Journal
ANNALS OF STATISTICS
Volume 43, Issue 1, Pages 215-237Publisher
INST MATHEMATICAL STATISTICS-IMS
DOI: 10.1214/14-AOS1274
Keywords
Network data; stochastic block model; spectral clustering; sparsity
Categories
Funding
- NSF [BCS-0941518, DMS-14-07771]
- NIH [MH057881]
- AFOSR
- DARPA [FA9550-12-1-0392]
- NSF CAREER Grant [DMS-11-49677]
- Division Of Mathematical Sciences
- Direct For Mathematical & Physical Scien [1407771] Funding Source: National Science Foundation
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available