Fast community detection by pseudo-likelihood

• Activity Number: 56
• Type: Invited
• Date/Time: Sunday, August 4, 2013 : 4:00 PM to 5:50 PM
• Sponsor: WNAR
• Author(s): Liza Levina *+
• Companies: University of Michigan
• Keywords: networks ; community detection ; pseudo-likelihood ; stochastic block models ; spectral clustering ; sparse graphs

Abstract

Many algorithms have been proposed for fitting network models with communities but most of them do not scale well to large networks, and many fail on sparse networks. Here we propose a new fast pseudo-likelihood method for fitting the stochastic block model, as well as a variant that allows for arbitrary degree distributions. The pseudo-likelihood algorithm performs well empirically under a range of settings, including on very sparse networks. It is also asymptotically consistent under reasonable conditions as long as the initial value is better than random guessing. To initialize the algorithm, we propose spectral clustering with perturbations, a new method of independent interest, which works well on sparse networks where regular spectral clustering fails. This is joint work with Arash Amini, Aiyou Chen, and Peter Bickel.