Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms

2015/03/02 by Emmanuel Abbe, Emmanuel Abbé, Abbe, Emmanuel +2 · 4 citations
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Opinion Dynamics and Social Influence #Probability (math.PR) #Random Matrices and Applications #Social and Information Networks (cs.SI) #cs.IT #cs.SI #math.IT #math.PR

paper · pdf · doi:10.48550/arxiv.1503.00609

openalex publication_date 2015/03/02 · arxiv created 2015/04/04 · arxiv updated 2015/04/07 · openalex created_date 2022/09/30 · openalex updated_date 2026/07/28

Abstract

New phase transition phenomena have recently been discovered for the stochastic block model, for the special case of two non-overlapping symmetric communities. This gives raise in particular to new algorithmic challenges driven by the thresholds. This paper investigates whether a general phenomenon takes place for multiple communities, without imposing symmetry. In the general stochastic block model SBM(n,p,Q), n vertices are split into k communities of relative size \p_i\_{i ∈ [k]}, and vertices in community i and j connect independently with probability \Q_i,j\_{i,j ∈ [k]}. This paper investigates the partial and exact recovery of communities in the general SBM (in the constant and logarithmic degree regimes), and uses the generality of the results to tackle overlapping communities. The contributions of the paper are: (i) an explicit characterization of the recovery threshold in the general SBM in terms of a new divergence function D₊, which generalizes the Hellinger and Chernoff divergences, and which provides an operational meaning to a divergence function analog to the KL-divergence in the channel coding theorem, (ii) the development of an algorithm that recovers the communities all the way down to the optimal threshold and runs in quasi-linear time, showing that exact recovery has no information-theoretic to computational gap for multiple communities, in contrast to the conjectures made for detection with more than 4 communities; note that the algorithm is optimal both in terms of achieving the threshold and in having quasi-linear complexity, (iii) the development of an efficient algorithm that detects communities in the constant degree regime with an explicit accuracy bound that can be made arbitrarily close to 1 when a prescribed signal-to-noise ratio (defined in term of the spectrum of \diag(p)Q) tends to infinity.

Citations

• Community Detection in the Labelled Stochastic Block Model
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Stochastic Block Models and Reconstruction
• Community structure in social and biological networks
• Information Recovery from Pairwise Measurements
• The Metropolis algorithm for graph bisection
• Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach

Cited by

• Community Recovery on Noisy Stochastic Block Models
• Learning Communities in the Presence of Errors
• Recovering Structured Probability Matrices
• Recovering communities in the general stochastic block model without knowing the parameters

Related

• Community Detection and Stochastic Block Models
• Recovering communities in the general stochastic block model without knowing the parameters
• Phase Transition for Stochastic Block Model with more than √(n) Communities (II)
• Stochastic block models with many communities and the Kesten--Stigum bound
• Algorithm independent bounds on community detection problems and associated transitions in stochastic block model graphs