Publication Type

Working Paper

Publication Date

10-2017

Abstract

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.

Keywords

Clustering, community detection, degree-corrected stochastic block model, k-means, regularization, strong consistency

Discipline

Econometrics

Research Areas

Econometrics

First Page

1

Last Page

53

Publisher

Singapore Management University Economics & Statistics Working Papers, No. 16-2017

City or Country

Singapore

Copyright Owner and License

Authors

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://arxiv.org/pdf/1710.06191.pdf

Included in

Econometrics Commons

Share

COinS