Pseudo-likelihood methods for community detection in large sparse networks
Venue
Annals of Statistics (2013), pp. 1-27
Publication Year
2013
Authors
Arash A Amini, Aiyou Chen, Peter Bickel, Liza Levina
BibTeX
Abstract
Many algorithms have been proposed for fitting network models with communities but
most of them do not scale well to large networks, and often fail on sparse
networks. Here we propose a new fast pseudo-likelihood method for fitting the
stochastic block model for networks, as well as a variant that allows for an
arbitrary degree distribution by conditioning on degrees. We show that the
algorithms perform well under a range of settings, including on very sparse
networks, and illustrate on the example of a network of political blogs. We also
propose spectral clustering with perturbations, a method of independent interest,
which works well on sparse networks where regular spectral clustering fails, and
use it to provide an initial value for pseudo-likelihood.
