mlsanityData to 7 Oct 2026

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

arXiv 1501.05021 ↗First posted 20 Jan 2015cs.DScited by 15

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 4; 2024: 2; 2025: 1; 2026: 2.

15 papers.

Sort:

  1. 2021Exact Recovery in the General Hypergraph Stochastic Block Modelcited by 13
  2. 2022Minimax Rates for Robust Community Detectioncited by 12
  3. 2021Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Modelcited by 7
  4. 2023Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptionscited by 7
  5. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  6. 2022Matrix Completion with Hierarchical Graph Side Informationcited by 5
  7. 2022The Multivariate Community Hawkes Model for Dependent Relational Events in Continuous-time Networkscited by 4
  8. 2022Community Recovery in the Geometric Block Modelcited by 2
  9. 2023Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labelscited by 2
  10. 2024Community detection with the Bethe-Hessiancited by 2
  11. 2024Community Detection in the Multi-View Stochastic Block Modelcited by 1
  12. 2023Variational Inference: Posterior Threshold Improves Network Clustering Accuracy in Sparse Regimescited by 0
3 more
  1. 2025Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animalscited by 0
  2. 2026Simplify to Amplify: Achieving Information-Theoretic Bounds with Fewer Steps in Spectral Community Detectioncited by 0
  3. 2026Query-Limited Community Recovery in Stochastic Block Modelscited by 0