A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
arXiv:1411.1469 · doi:10.5705/ss.202015.0279
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 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.
arXiv comment19 pages
References in corpus (10)
- Finding and evaluating community structure in networks
- Stochastic blockmodels and community structure in networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Fast community detection by SCORE
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Stochastic Block Models and Reconstruction
- Model Selection for Degree-corrected Block Models
- A Tensor Approach to Learning Mixed Membership Community Models
- Hypergeometric tail inequalities: ending the insanity
Cited by in corpus (9)
- A goodness-of-fit test for stochastic block models
- Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
- Achieving Optimal Misclassification Proportion in Stochastic Block Model
- PECOK: a convex optimization approach to variable clustering
- Network Cross-Validation for Determining the Number of Communities in Network Data
- Linear regression and its inference on noisy network-linked data
- Community models for networks observed through edge nominations
- Adjusted chi-square test for degree-corrected block models
- Fast Network Community Detection with Profile-Pseudo Likelihood Methods