# Information-theoretic thresholds for community detection in sparse networks

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jan 2016.

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

- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [Correlation detection in trees for planted graph alignment](https://mlsanity.com/paper/2107.07623/) (2021)
- [Phase transitions in the mini-batch size for sparse and dense two-layer neural networks](https://mlsanity.com/paper/2305.06435/) (2023)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)
- [Low degree conjecture implies sharp computational thresholds in stochastic block model](https://mlsanity.com/paper/2502.15024/) (2025)
- [Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models](https://mlsanity.com/paper/2108.04729/) (2021)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [On the Fundamental Limits of Exact Inference in Structured Prediction](https://mlsanity.com/paper/2102.08895/) (2021)
- [Robust Correlation Clustering with Asymmetric Noise](https://mlsanity.com/paper/2110.08385/) (2021)
- [Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold](https://mlsanity.com/paper/2205.11677/) (2022)
- [Overlapping Community Detection using Dynamic Dilated Aggregation in Deep Residual GCN](https://mlsanity.com/paper/2210.11174/) (2022)
- [Multi-View Stochastic Block Models](https://mlsanity.com/paper/2406.04860/) (2024)
- [Query-Limited Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/2606.02055/) (2026)

## Abstract (arXiv)

We give upper and lower bounds on the information-theoretic threshold for community detection in the stochastic block model. Specifically, let k be the number of groups, d be the average degree, the probability of edges between vertices within and between groups be cin/n and cout/n respectively, and let λ = (cin-cout)/(kd). We show that, when k is large, and λ = O(1/k), the critical value of d at which community detection becomes possible -- in physical terms, the condensation threshold -- is [ dc = Theta!left( fraclog kk λ2 right) , , ] with tighter results in certain regimes. Above this threshold, we show that the only partitions of the nodes into k groups are correlated with the ground truth, giving an exponential-time algorithm that performs better than chance -- in particular, detection is possible for k ≥ 5 in the disassortative case λ < 0 and for k ≥ 11 in the assortative case λ > 0. (Similar upper bounds were obtained independently by Abbe and Sandon.) Below this threshold, we use recent results of Neeman and Netrapalli (who generalized arguments of Mossel, Neeman, and Sly) to show that no algorithm can label the vertices better than chance, or even distinguish the block model from an ErdHos-R'enyi random graph with high probability. We also rely on bounds on certain functions of doubly stochastic matrices due to Achlioptas and Naor; indeed, our lower bound on dc is the second moment lower bound on the k-colorability threshold for random graphs with a certain effective degree.