A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models

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 $\log n$ 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.

19 pages

References in corpus (2)

• Stochastic blockmodels and community structure in networks
• 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