# Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2015.

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

- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [The Multivariate Community Hawkes Model for Dependent Relational Events in Continuous-time Networks](https://mlsanity.com/paper/2205.00639/) (2022)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [Community Recovery in the Geometric Block Model](https://mlsanity.com/paper/2206.11303/) (2022)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Community Detection in the Multi-View Stochastic Block Model](https://mlsanity.com/paper/2401.09510/) (2024)
- [Variational Inference: Posterior Threshold Improves Network Clustering Accuracy in Sparse Regimes](https://mlsanity.com/paper/2301.04771/) (2023)
- [Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals](https://mlsanity.com/paper/2509.15989/) (2025)
- [Simplify to Amplify: Achieving Information-Theoretic Bounds with Fewer Steps in Spectral Community Detection](https://mlsanity.com/paper/2602.17104/) (2026)
- [Query-Limited Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/2606.02055/) (2026)

## Abstract (arXiv)

In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with k blocks, for any k fixed. Our algorithm works with graphs having constant edge density, under an optimal condition on the gap between the density inside a block and the density between the blocks. As a co-product, we settle an open question posed by Abbe et. al. concerning censor block models.