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

arXiv: https://arxiv.org/abs/1503.00609 · HTML: https://mlsanity.com/paper/1503.00609/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2015.

## Built on by (most cited first, 5 of 5)

- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model](https://mlsanity.com/paper/2102.13135/) (2021)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)
- [Exact Recovery of Community Detection in dependent Gaussian Mixture Models](https://mlsanity.com/paper/2209.14859/) (2022)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)

## Abstract (arXiv)

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 pii ∈ [k], and vertices in community i and j connect independently with probability Qi,ji,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.