Consistency of spectral clustering in stochastic block models

Abstract

We analyze the performance of spectral clustering for community extraction in stochastic block models. We show that, under mild conditions, spectral clustering applied to the adjacency matrix of the network can consistently recover hidden communities even when the order of the maximum expected degree is as small as $\log n$, with $n$ the number of nodes. This result applies to some popular polynomial time spectral clustering algorithms and is further extended to degree corrected stochastic block models using a spherical $k$-median spectral clustering method. A key component of our analysis is a combinatorial bound on the spectrum of binary random matrices, which is sharper than the conventional matrix Bernstein inequality and may be of independent interest.

Published in at http://dx.doi.org/10.1214/14-AOS1274 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Stochastic blockmodels and community structure in networks
• Consistency of spectral clustering in stochastic block models
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time

Cited by in corpus (52)

• Consistency of spectral clustering in stochastic block models
• Rate-optimal graphon estimation
• A goodness-of-fit test for stochastic block models
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• A Survey on Theoretical Advances of Community Detection in Networks
• Detecting Dynamic Community Structure in Functional Brain Networks Across Individuals: A Multilayer Approach
• Threefold way to the dimension reduction of dynamics on networks: an application to synchronization
• A global synchronization theorem for oscillators on a random graph
• Blind identification of stochastic block models from dynamical observations
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Consistent structure estimation of exponential-family random graph models with block structure
• Community detection by spectral methods in multi-layer networks
• Large-scale estimation of random graph models with local dependence
• Multi-Scale Factor Analysis of High-Dimensional Brain Signals
• Community detection for weighted bipartite networks
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Sparse Representation Classification Beyond L1 Minimization and the Subspace Assumption
• Pairwise Covariates-adjusted Block Model for Community Detection
• Sparse random tensors: Concentration, regularization and applications
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel
• Mixed Membership Graph Clustering via Systematic Edge Query
• A useful criterion on studying consistent estimation in community detection
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Entrograms and coarse graining of dynamics on complex networks
• Covariance Matrix Estimation for High-Throughput Biomedical Data with Interconnected Communities
• Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model
• Estimating the number of communities in weighted networks
• Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Next Waves in Veridical Network Embedding
• How social networks influence human behavior: An integrated latent space approach for differential social influence
• Comparing Graph Spectra of Adjacency and Laplacian Matrices
• A network community detection method with integration of data from multiple layers and node attributes
• Efficient inference in stochastic block models with vertex labels
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• On role extraction for digraphs via neighbourhood pattern similarity
• Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
• Factor-Driven Network Informed Restricted Vector Autoregression
• Modularity in planted partition model
• Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks
• Testing Simultaneous Diagonalizability
• Overlapping community detection in networks via sparse spectral decomposition
• Mode Reduction for Markov Jump Systems
• A Unified Framework for Community Detection and Model Selection in Blockmodels
• Consistent model selection for the Degree Corrected Stochastic Blockmodel
• Overlapping community detection in weighted networks
• Co-factor analysis of citation networks