Publication Type
Journal Article
Version
submittedVersion
Publication Date
1-2020
Abstract
In this paper we prove the strong consistency of several methods based on the spectral clustering techniques that are widely used to study the community detection problem in stochastic block models (SBMs). We show that under some weak conditions on the minimal degree, the number of communities, and the eigenvalues of the probability block matrix, the K-means algorithm applied to the eigenvectors of the graph Laplacian associated with its first few largest eigenvalues can classify all individuals into the true community uniformly correctly almost surely. Extensions to both regularized spectral clustering and degree-corrected SBMs are also considered. We illustrate the performance of different methods on simulated networks.
Keywords
Community detection, degree-corrected stochastic block model, K-means, regularization, strong consistency.
Discipline
Econometrics
Research Areas
Econometrics
Publication
IEEE Transactions on Information Theory
Volume
66
Issue
1
First Page
324
Last Page
338
ISSN
0018-9448
Identifier
10.1109/TIT.2019.2934157
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Citation
SU, Liangjun; WANG, Wuyi; and ZHANG, Yichong.
Strong consistency of spectral clustering for stochastic block models. (2020). IEEE Transactions on Information Theory. 66, (1), 324-338.
Available at: https://ink.library.smu.edu.sg/soe_research/2317
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/TIT.2019.2934157
Comments
PDF includes supplement with proofs, lemmas and additional simulation results.