A spectral method for community detection in moderately-sparse degree-corrected stochastic block models

06/29/2015
by   Lennart Gulikers, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset