Consistency of spectral clustering in stochastic block models

2013/12/31 by Jing Lei, Alessandro Rinaldo · 3 citations
Mathematics · #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.1214/14-aos1274

published as Annals of Statistics 2015, Vol. 43, No. 1, 215-237 · 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)

arxiv created 2014/12/30 · arxiv updated 2014/12/31

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.

Cited by

• Spectral clustering of network time series via the sample covariance matrix
• Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy
• Towards Anomaly-Aware Pre-Training and Fine-Tuning for Graph Anomaly Detection

Related

• Strong Consistency of Spectral Clustering for Stochastic Block Models
• A spectral method for community detection in moderately-sparse degree-corrected stochastic block models
• Fundamental Limits of Spectral Clustering in Stochastic Block Models
• Strong Consistency, Graph Laplacians, and the Stochastic Block Model
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting