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 (13)

• Finding and evaluating community structure in networks
• Stochastic blockmodels and community structure in networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• User-friendly tail bounds for sums of random matrices
• Spectral redemption: clustering sparse networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistency of spectral clustering in stochastic block models
• Fast community detection by SCORE
• Consistency of community detection in networks under degree-corrected stochastic block models
• Stochastic blockmodels with growing number of classes
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Minimax sparse principal subspace estimation in high dimensions
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time

Cited by in corpus (53)

• 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
• Blind identification of stochastic block models from dynamical observations
• A global synchronization theorem for oscillators on a random graph
• 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
• Large-scale estimation of random graph models with local dependence
• Community detection by spectral methods in multi-layer networks
• 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
• A useful criterion on studying consistent estimation in community detection
• Mixed Membership Graph Clustering via Systematic Edge Query
• Profile Likelihood Biclustering
• 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
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Estimating the number of communities in weighted networks
• Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits
• Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model
• 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
• Efficient inference in stochastic block models with vertex labels
• A network community detection method with integration of data from multiple layers and node attributes
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• On role extraction for digraphs via neighbourhood pattern similarity
• Testing Simultaneous Diagonalizability
• 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
• Overlapping community detection in networks via sparse spectral decomposition
• Mode Reduction for Markov Jump Systems
• Overlapping community detection in weighted networks
• Consistent model selection for the Degree Corrected Stochastic Blockmodel
• Co-factor analysis of citation networks
• A Unified Framework for Community Detection and Model Selection in Blockmodels