Strong consistency of spectral clustering for stochastic block models

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...

Full description

Saved in:
Bibliographic Details
Main Authors: SU, Liangjun, WANG, Wuyi, ZHANG, Yichong
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2020
Subjects:
Online Access:https://ink.library.smu.edu.sg/soe_research/2317
https://ink.library.smu.edu.sg/context/soe_research/article/3316/viewcontent/Strong_consistency_Stochastic_Block_modles_2019_wp.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.soe_research-3316
record_format dspace
spelling sg-smu-ink.soe_research-33162021-04-19T05:04:24Z Strong consistency of spectral clustering for stochastic block models SU, Liangjun WANG, Wuyi ZHANG, Yichong 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. 2020-01-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/soe_research/2317 info:doi/10.1109/TIT.2019.2934157 https://ink.library.smu.edu.sg/context/soe_research/article/3316/viewcontent/Strong_consistency_Stochastic_Block_modles_2019_wp.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Economics eng Institutional Knowledge at Singapore Management University Community detection degree-corrected stochastic block model K-means regularization strong consistency. Econometrics
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Community detection
degree-corrected stochastic block model
K-means
regularization
strong consistency.
Econometrics
spellingShingle Community detection
degree-corrected stochastic block model
K-means
regularization
strong consistency.
Econometrics
SU, Liangjun
WANG, Wuyi
ZHANG, Yichong
Strong consistency of spectral clustering for stochastic block models
description 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.
format text
author SU, Liangjun
WANG, Wuyi
ZHANG, Yichong
author_facet SU, Liangjun
WANG, Wuyi
ZHANG, Yichong
author_sort SU, Liangjun
title Strong consistency of spectral clustering for stochastic block models
title_short Strong consistency of spectral clustering for stochastic block models
title_full Strong consistency of spectral clustering for stochastic block models
title_fullStr Strong consistency of spectral clustering for stochastic block models
title_full_unstemmed Strong consistency of spectral clustering for stochastic block models
title_sort strong consistency of spectral clustering for stochastic block models
publisher Institutional Knowledge at Singapore Management University
publishDate 2020
url https://ink.library.smu.edu.sg/soe_research/2317
https://ink.library.smu.edu.sg/context/soe_research/article/3316/viewcontent/Strong_consistency_Stochastic_Block_modles_2019_wp.pdf
_version_ 1770574860624330752