Generic sample splitting for refined community recovery in degree corrected stochastic block models

DOI10.5705/SS.202015.0279zbMATH Open1392.62187arXiv1411.1469OpenAlexW1546146584MaRDI QIDQ4601244FDOQ4601244

Authors: Jing Lei, Lingxue Zhu 

Publication date: 12 January 2018

Published in: STATISTICA SINICA (Search for Journal in Brave)

Abstract: We propose and analyze a generic method for community recovery in stochastic block models and degree corrected block models. This approach can exactly recover the hidden communities with high probability when the expected node degrees are of order $logn$ or higher. Starting from a roughly correct community partition given by some conventional community recovery algorithm, this method refines the partition in a cross clustering step. Our results simplify and extend some of the previous work on exact community recovery, discovering the key role played by sample splitting. The proposed method is simple and can be implemented with many practical community recovery algorithms.

Full work available at URL: https://arxiv.org/abs/1411.1469

Recommendations

• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Consistency of spectral clustering in stochastic block models
• Community detection and stochastic block models: recent developments
• Convexified modularity maximization for degree-corrected stochastic block models
• Community detection and stochastic block models

zbMATH Keywords

clusteringcommunity detectionblock modelssample splittingnetwork data

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Estimation in multivariate analysis (62H12)

Cited In (4)

• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Uniform estimation in stochastic block models is slow
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models

This page was built for publication: Generic sample splitting for refined community recovery in degree corrected stochastic block models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601244)