# Community Detection and Stochastic Block Models

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

## Key facts

- Cited by 319 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2017.

## Built on by (most cited first, 30 of 319)

- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [New Benchmarks for Learning on Non-Homophilous Graphs](https://mlsanity.com/paper/2104.01404/) (2021)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Connect, Not Collapse: Explaining Contrastive Learning for Unsupervised Domain Adaptation](https://mlsanity.com/paper/2204.00570/) (2022)
- [A Comprehensive Survey on Community Detection with Deep Learning](https://mlsanity.com/paper/2105.12584/) (2021)
- [GraphWorld: Fake Graphs Bring Real Insights for GNNs](https://mlsanity.com/paper/2203.00112/) (2022)
- [A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning](https://mlsanity.com/paper/2101.01669/) (2021)
- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [Generalised Implicit Neural Representations](https://mlsanity.com/paper/2205.15674/) (2022)
- [Network Formation and Dynamics Among Multi-LLMs](https://mlsanity.com/paper/2402.10659/) (2024)
- [Rethinking Graph Neural Architecture Search from Message-passing](https://mlsanity.com/paper/2103.14282/) (2021)
- [Curvature Graph Neural Network](https://mlsanity.com/paper/2106.15762/) (2021)
- [FedGCN: Convergence-Communication Tradeoffs in Federated Training of Graph Convolutional Networks](https://mlsanity.com/paper/2201.12433/) (2022)
- [Graph Attention Retrospective](https://mlsanity.com/paper/2202.13060/) (2022)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [Beyond Real-world Benchmark Datasets: An Empirical Study of Node Classification with GNNs](https://mlsanity.com/paper/2206.09144/) (2022)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Unconditional Scene Graph Generation](https://mlsanity.com/paper/2108.05884/) (2021)
- [Modularity-Aware Graph Autoencoders for Joint Community Detection and Link Prediction](https://mlsanity.com/paper/2202.00961/) (2022)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [A Neural Collapse Perspective on Feature Evolution in Graph Neural Networks](https://mlsanity.com/paper/2307.01951/) (2023)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)

## Abstract (arXiv)

The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in combinatorial statistics and more generally data science. This monograph surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational tradeoffs, and for various recovery requirements such as exact, partial and weak recovery. The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal SNR-mutual information tradeoff for partial recovery, and the gap between information-theoretic and computational thresholds. The monograph gives a principled derivation of the main algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, (linearized) belief propagation, classical/nonbacktracking spectral methods and graph powering. Extensions to other block models, such as geometric block models, and a few open problems are also discussed.