Strong Consistency, Graph Laplacians, and the Stochastic Block Model
This provides theoretical guarantees for community detection in networks, but it is incremental as it builds on existing spectral clustering methods.
The paper tackles the problem of when spectral clustering via graph Laplacians can exactly recover hidden communities in the stochastic block model, proving it achieves exact recovery under conditions matching information-theoretic limits.
Spectral clustering has become one of the most popular algorithms in data clustering and community detection. We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the stochastic block model. Our aim is to answer the following question: when is spectral clustering via the graph Laplacian able to achieve strong consistency, i.e., the exact recovery of the underlying hidden communities? Our work provides an entrywise analysis (an $\ell_{\infty}$-norm perturbation bound) of the Fielder eigenvector of both the unnormalized and the normalized Laplacian associated with the adjacency matrix sampled from the stochastic block model. We prove that spectral clustering is able to achieve exact recovery of the planted community structure under conditions that match the information-theoretic limits.