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

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 $\text{SBM}(n,p,Q)$, $n$ vertices are split into $k$ communities of relative size $\{p_i{\}}_{i\in [k]}$, and vertices in community $i$ and $j$ connect independently with probability $\{Q_{i,j}{\}}_{i,j\in [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.

References in corpus (12)

• Community structure in social and biological networks
• Stochastic blockmodels and community structure in networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Stochastic Block Models and Reconstruction
• Near-Optimal Joint Object Matching via Convex Relaxation
• Community Detection in the Labelled Stochastic Block Model
• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
• Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
• Tight Error Bounds for Structured Prediction
• Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach
• Information Recovery from Pairwise Measurements

Cited by in corpus (22)

• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Private Graphon Estimation for Sparse Graphs
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Density Evolution in the Degree-correlated Stochastic Block Model
• Community Recovery in Graphs with Locality
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• Recovering communities in the general stochastic block model without knowing the parameters
• Community detection with nodal information
• Active Learning for Community Detection in Stochastic Block Models
• Learning Communities in the Presence of Errors
• Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models
• Estimating Graph Dimension with Cross-validated Eigenvalues
• Recovering Structured Probability Matrices
• Community Detection Using Slow Mixing Markov Models
• Local Algorithms for Block Models with Side Information
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• Revisiting Spectral Graph Clustering with Generative Community Models
• Interactive and Iterative Discovery of Entity Network Subgraphs
• EXIT Analysis for Community Detection