A spectral method for community detection in moderately-sparse degree-corrected stochastic block models
This work addresses community detection in networks with degree heterogeneity, offering a parameter-free method that does not require prior knowledge of the number of communities, though it appears incremental relative to existing spectral methods.
The authors tackled community detection in Degree-Corrected Stochastic Block Models by proposing a spectral clustering algorithm that consistently recovers block-membership for all but a vanishing fraction of nodes, with success in regimes where the lowest degree is of order log(n) or higher and for heterogeneous degree distributions.
We consider community detection in Degree-Corrected Stochastic Block Models (DC-SBM). We propose a spectral clustering algorithm based on a suitably normalized adjacency matrix. We show that this algorithm consistently recovers the block-membership of all but a vanishing fraction of nodes, in the regime where the lowest degree is of order log$(n)$ or higher. Recovery succeeds even for very heterogeneous degree-distributions. The used algorithm does not rely on parameters as input. In particular, it does not need to know the number of communities.