# Strong Consistency of Spectral Clustering for Stochastic Block Models

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

## Key facts

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

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

- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [A statistically consistent measure of semantic uncertainty using Language Models](https://mlsanity.com/paper/2502.00507/) (2025)
- [Strongly Consistent Community Detection in Popularity Adjusted Block Models](https://mlsanity.com/paper/2506.07224/) (2025)
- [Perfect Spectral Clustering with Discrete Covariates](https://mlsanity.com/paper/2205.08047/) (2022)
- [Multi-Frequency Joint Community Detection and Phase Synchronization](https://mlsanity.com/paper/2206.12276/) (2022)
- [From topology learning to graph generation: A unifying perspective](https://mlsanity.com/paper/2609.02286/) (2026)
- [Exact Community Recovery in Bipartite Networks](https://mlsanity.com/paper/2609.12445/) (2026)

## Abstract (arXiv)

In this paper we prove the strong consistency of several methods based on the spectral clustering techniques that are widely used to study the community detection problem in stochastic block models (SBMs). We show that under some weak conditions on the minimal degree, the number of communities, and the eigenvalues of the probability block matrix, the K-means algorithm applied to the eigenvectors of the graph Laplacian associated with its first few largest eigenvalues can classify all individuals into the true community uniformly correctly almost surely. Extensions to both regularized spectral clustering and degree-corrected SBMs are also considered. We illustrate the performance of different methods on simulated networks.