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)

Copyright Owner and License

Authors

Comments

PDF includes supplement with proofs, lemmas and additional simulation results.

Additional URL

https://doi.org/10.1109/TIT.2019.2934157

Included in

Econometrics Commons

Share

COinS