Strong Consistency of Spectral Clustering for Stochastic Block Models

Liangjun Su (), 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

Abstract: 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
Date: 2017-10-20
New Economics Papers: this item is included in nep-sea
References: Add references at CitEc
Citations:

Downloads: (external link)
http://ink.library.smu.edu.sg/soe_research/2118/ Full text (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

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 ( this e-mail address is bad, please contact ).