Strong consistency of spectral clustering for stochastic block models
In this paper we prove the strong consistency of several methods based on thespectral clustering techniques that are widely used to study the communitydetection problem in stochastic block models (SBMs). We show that under someweak conditions on the minimal degree, the number of communities, and the...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2017
|
| Subjects: | |
| Online Access: | https://ink.library.smu.edu.sg/soe_research/2102 https://ink.library.smu.edu.sg/context/soe_research/article/3102/viewcontent/StrongConsistencySpectralClustering_2017_wp.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | In this paper we prove the strong consistency of several methods based on thespectral clustering techniques that are widely used to study the communitydetection problem in stochastic block models (SBMs). We show that under someweak conditions on the minimal degree, the number of communities, and theeigenvalues of the probability block matrix, the K-means algorithm applied tothe Eigenvectors of the graph Laplacian associated with its first few largesteigenvalues can classify all individuals into the true community uniformlycorrectly almost surely. Extensions to both regularized spectral clustering anddegree-corrected SBMs are also considered. We illustrate the performance ofdifferent methods on simulated networks. |
|---|