Strong Consistency, Graph Laplacians, and the Stochastic Block Model

Abstract

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.

References in corpus (8)

• The structure and function of complex networks
• Community structure in social and biological networks
• Community detection in graphs
• Benchmark graphs for testing community detection algorithms
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Near-optimal bounds for phase synchronization
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms