Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová
Phys. Rev. E 84, 066106 – Published 12 December 2011

Abstract

In this paper we extend our previous work on the stochastic block model, a commonly used generative model for social and biological networks, and the problem of inferring functional groups or communities from the topology of the network. We use the cavity method of statistical physics to obtain an asymptotically exact analysis of the phase diagram. We describe in detail properties of the detectability-undetectability phase transition and the easy-hard phase transition for the community detection problem. Our analysis translates naturally into a belief propagation algorithm for inferring the group memberships of the nodes in an optimal way, i.e., that maximizes the overlap with the underlying group memberships, and learning the underlying parameters of the block model. Finally, we apply the algorithm to two examples of real-world networks and discuss its performance.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
2 More
  • Received 14 September 2011

DOI:https://doi.org/10.1103/PhysRevE.84.066106

©2011 American Physical Society

Authors & Affiliations

Aurelien Decelle1, Florent Krzakala2, Cristopher Moore3, and Lenka Zdeborová4,*

  • 1Université Paris-Sud & CNRS, LPTMS, UMR8626, Bât. 100, Université Paris-Sud F-91405 Orsay, France
  • 2CNRS and ESPCI ParisTech, 10 rue Vauquelin, UMR 7083 Gulliver, Paris F-75000, France
  • 3Santa Fe Institute and University of New Mexico, Albuquerque, New Mexico, USA
  • 4Institut de Physique Théorique, IPhT, CEA Saclay, and URA 2306, CNRS, F-91191 Gif-sur-Yvette, France

  • *lenka.zdeborova@cea.fr

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 84, Iss. 6 — December 2011

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×