Strong Consistency of Spectral Clustering for Stochastic Block Models
Wuyi Wang and
Yichong Zhang ()
Additional contact information
Wuyi Wang: School of Economics, Singapore Management University
Yichong Zhang: School of Economics, Singapore Management University
No 16-2017, Economics and Statistics Working Papers from Singapore Management University, School of Economics
In this paper we prove the strong consistency of several method 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 rst 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.
Pages: 57 pages
New Economics Papers: this item is included in nep-sea
References: Add references at CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
http://ink.library.smu.edu.sg/soe_research/2118/ Full text (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:ris:smuesw:2017_016
Access Statistics for this paper
More papers in Economics and Statistics Working Papers from Singapore Management University, School of Economics 90 Stamford Road, Sigapore 178903. Contact information at EDIRC.
Bibliographic data for series maintained by Cheong Pei Qi ().