Community detection in sparse random networks

DOI10.1214/14-AAP1080zbMath1326.05145arXiv1405.1478MaRDI QIDQ894814

Ery Arias-Castro, Nicolas Verzelen

Publication date: 24 November 2015

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.1478

zbMATH Keywords

community detection; minimax hypothesis testing; scan statistic; Erdős-Rényi random graph; largest connected component; detecting a dense subgraph; planted subgraph problem

Mathematics Subject Classification ID

05C82: Small world graphs, complex networks (graph-theoretic aspects)

05C80: Random graphs (graph-theoretic aspects)

62C20: Minimax procedures in statistical decision theory

05C42: Density (toughness, etc.)

Related Items

Test dense subgraphs in sparse uniform hypergraph, Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes, Testing correlation of unlabeled random graphs, Two-sample Hypothesis Testing for Inhomogeneous Random Graphs, Spectral clustering in the dynamic stochastic block model, Finding one community in a sparse graph, Community detection in sparse random networks, Detection thresholds for the \(\beta\)-model on sparse graphs, Optimality and sub-optimality of PCA. I: Spiked random matrix models, Detecting a planted community in an inhomogeneous random graph, Detecting a botnet in a network, Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials, Tensor clustering with planted structures: statistical optimality and computational limits, Uniform estimation in stochastic block models is slow, Computational barriers to estimation from low-degree polynomials, Hypothesis testing in sparse weighted stochastic block model, Statistical limits of spiked tensor models, Cliques in rank-1 random graphs: the role of inhomogeneity, Computational barriers in minimax submatrix detection, Sharp detection boundaries on testing dense subhypergraph

Cites Work

• Belief propagation, robust reconstruction and optimal recovery of block models
• Optimal detection of sparse principal components in high dimension
• Community detection in sparse random networks
• Bayesian anomaly detection methods for social networks
• Counting connected graphs inside-out
• Moment inequalities for functions of independent random variables
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Community detection in dense random networks
• Random Graphs and Complex Networks
• A nonparametric view of network models and Newman–Girvan and other modularities
• On the Limiting Distribution of a Graph Scan Statistic
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Community structure in social and biological networks
• Finding Hidden Cliques in Linear Time with High Probability
• Testing Statistical Hypotheses
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item