A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
This work addresses community detection in network analysis, offering an incremental improvement by simplifying and extending prior methods for exact recovery.
The paper tackles the problem of exact community recovery in stochastic block models by proposing a generic sample splitting method that refines initial partitions, achieving exact recovery with high probability when expected node degrees are of order log n or higher.
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.