2014/04/25 by Joe Neeman, Praneeth Netrapalli, Neeman, Joe +1 · 1 citation
Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #Social and Information Networks (cs.SI) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.1404.6304
openalex publication_date 2014/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of clustering (or reconstruction) in the stochastic block model, in the regime where the average degree is constant. For the case of two clusters with equal sizes, recent results by Mossel, Neeman and Sly, and by Massoulie, show that reconstructability undergoes a phase transition at the Kesten-Stigum bound of λ22 d = 1, where λ2 is the second largest eigenvalue of a related stochastic matrix and d is the average degree. In this paper, we address the general case of more than two clusters and/or unbalanced cluster sizes. Our main result is a sufficient condition for clustering to be impossible, which matches the existing result for two clusters of equal sizes. A key ingredient in our result is a new connection between non-reconstructability and non-distinguishability of the block model from an Erdős-Rényi model with the same average degree. We also show that it is some times possible to reconstruct even when λ22 d < 1. Our results provide evidence supporting a series of conjectures made by Decelle, Krzkala, Moore and Zdeborová regarding reconstructability and distinguishability of stochastic block models (but do not settle them).