Determining the number of communities in degree-corrected stochastic block models

We propose to estimate the number of communities in degree-corrected stochastic block models based on a pseudo likelihood ratio. For estimation, we consider a spectral clustering together with binary segmentation method. This approach guarantees an upper bound for the pseudo likelihood ratio statist...

Full description

Saved in:
Bibliographic Details
Main Authors: MA, Shujie, SU, Liangjun, ZHANG, Yichong
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2021
Subjects:
Online Access:https://ink.library.smu.edu.sg/soe_research/2485
https://ink.library.smu.edu.sg/context/soe_research/article/3484/viewcontent/20_037_pvoa.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-3484
record_format dspace
spelling sg-smu-ink.soe_research-34842022-03-25T01:12:52Z Determining the number of communities in degree-corrected stochastic block models MA, Shujie SU, Liangjun ZHANG, Yichong We propose to estimate the number of communities in degree-corrected stochastic block models based on a pseudo likelihood ratio. For estimation, we consider a spectral clustering together with binary segmentation method. This approach guarantees an upper bound for the pseudo likelihood ratio statistic when the model is over-fitted. We also derive its limiting distribution when the model is under-fitted. Based on these properties, we establish the consistency of our estimator for the true number of communities. Developing these theoretical properties require a mild condition on the average degree: growing at a rate faster than log(n), where n is the number of nodes. Our proposed method is further illustrated by simulation studies and analysis of real-world networks. The numerical results show that our approach has satisfactory performance when the network is sparse and/or has unbalanced communities. 2021-04-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/soe_research/2485 https://ink.library.smu.edu.sg/context/soe_research/article/3484/viewcontent/20_037_pvoa.pdf http://creativecommons.org/licenses/by/4.0/ Research Collection School Of Economics eng Institutional Knowledge at Singapore Management University Clustering community detection degree-corrected stochastic block model K-means regularization Computer Sciences Econometrics
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Clustering
community detection
degree-corrected stochastic block model
K-means
regularization
Computer Sciences
Econometrics
spellingShingle Clustering
community detection
degree-corrected stochastic block model
K-means
regularization
Computer Sciences
Econometrics
MA, Shujie
SU, Liangjun
ZHANG, Yichong
Determining the number of communities in degree-corrected stochastic block models
description We propose to estimate the number of communities in degree-corrected stochastic block models based on a pseudo likelihood ratio. For estimation, we consider a spectral clustering together with binary segmentation method. This approach guarantees an upper bound for the pseudo likelihood ratio statistic when the model is over-fitted. We also derive its limiting distribution when the model is under-fitted. Based on these properties, we establish the consistency of our estimator for the true number of communities. Developing these theoretical properties require a mild condition on the average degree: growing at a rate faster than log(n), where n is the number of nodes. Our proposed method is further illustrated by simulation studies and analysis of real-world networks. The numerical results show that our approach has satisfactory performance when the network is sparse and/or has unbalanced communities.
format text
author MA, Shujie
SU, Liangjun
ZHANG, Yichong
author_facet MA, Shujie
SU, Liangjun
ZHANG, Yichong
author_sort MA, Shujie
title Determining the number of communities in degree-corrected stochastic block models
title_short Determining the number of communities in degree-corrected stochastic block models
title_full Determining the number of communities in degree-corrected stochastic block models
title_fullStr Determining the number of communities in degree-corrected stochastic block models
title_full_unstemmed Determining the number of communities in degree-corrected stochastic block models
title_sort determining the number of communities in degree-corrected stochastic block models
publisher Institutional Knowledge at Singapore Management University
publishDate 2021
url https://ink.library.smu.edu.sg/soe_research/2485
https://ink.library.smu.edu.sg/context/soe_research/article/3484/viewcontent/20_037_pvoa.pdf
_version_ 1770575778566635520