A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Beyond Data Splitting: Full-Data Conformal Prediction by Differential Privacy
Privacy protection and uncertainty quantification are increasingly important in data-driven decision making. Conformal prediction provides finite-sample marginal coverage, but existing private approaches often rely on da…
Decision MakingRefined Graph Encoder Embedding via Self-Training and Latent Community Recovery
This paper introduces a refined graph encoder embedding method, enhancing the original graph encoder embedding through linear transformation, self-training, and hidden community recovery within observed communities. We p…
Strongly Consistent Community Detection in Popularity Adjusted Block Models
The Popularity Adjusted Block Model (PABM) provides a flexible framework for community detection in network data by allowing heterogeneous node popularity across communities. However, this flexibility increases model com…
ClusteringCommunity DetectionConvergence Guarantees for Non-Convex Optimisation with Cauchy-Based Penalties
In this paper, we propose a proximal splitting methodology with a non-convex penalty function based on the heavy-tailed Cauchy distribution. We first suggest a closed-form expression for calculating the proximal operator…
DenoisingImage ReconstructionCommunity Detection and Stochastic Block Models
The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fer…
ClusteringCommunity DetectionStochastic Block Model