# Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2014.

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

- [A Neural Collapse Perspective on Feature Evolution in Graph Neural Networks](https://mlsanity.com/paper/2307.01951/) (2023)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [A Comprehensive Review of Community Detection in Graphs](https://mlsanity.com/paper/2309.11798/) (2023)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)
- [Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method](https://mlsanity.com/paper/2112.14204/) (2021)
- [Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information](https://mlsanity.com/paper/2201.05923/) (2022)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [Spectral Algorithms Optimally Recover Planted Sub-structures](https://mlsanity.com/paper/2203.11847/) (2022)
- [Multi-Frequency Joint Community Detection and Phase Synchronization](https://mlsanity.com/paper/2206.12276/) (2022)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (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)

## Abstract (arXiv)

We consider the problem of community detection in the Stochastic Block Model with a finite number K of communities of sizes linearly growing with the network size n. This model consists in a random graph such that each pair of vertices is connected independently with probability p within communities and q across communities. One observes a realization of this random graph, and the objective is to reconstruct the communities from this observation. We show that under spectral algorithms, the number of misclassified vertices does not exceed s with high probability as n grows large, whenever pn=ω(1), s=o(n) and beginequation* liminfn→∞ n(α1 p+α2 q-(α1 + α2)p^fracα1α1 + α2q^fracα2α1 + α2)over log (fracns) >1,quadquad(1) endequation* where α1 and α2 denote the (fixed) proportions of vertices in the two smallest communities. In view of recent work by Abbe et al. and Mossel et al., this establishes that the proposed spectral algorithms are able to exactly recover communities whenever this is at all possible in the case of networks with two communities with equal sizes. We conjecture that condition (1) is actually necessary to obtain less than s misclassified vertices asymptotically, which would establish the optimality of spectral method in more general scenarios.