• Featured in Physics

Efficient and principled method for detecting communities in networks

Brian Ball, Brian Karrer, and M. E. J. Newman
Phys. Rev. E 84, 036103 – Published 8 September 2011
Physics logo See Synopsis: Community spirit

Abstract

A fundamental problem in the analysis of network data is the detection of network communities, groups of densely interconnected nodes, which may be overlapping or disjoint. Here we describe a method for finding overlapping communities based on a principled statistical approach using generative network models. We show how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasonable running times. We test the method both on real-world networks and on synthetic benchmarks and find that it gives results competitive with previous methods. We also show that the same approach can be used to extract nonoverlapping community divisions via a relaxation method, and demonstrate that the algorithm is competitively fast and accurate for the nonoverlapping problem.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 27 April 2011

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

©2011 American Physical Society

Synopsis

Key Image

Community spirit

Published 8 September 2011

A new algorithm is able to efficiently identify the clusters of nodes, called communities, that tend to form in networks.

See more in Physics

Authors & Affiliations

Brian Ball1, Brian Karrer1, and M. E. J. Newman1,2

  • 1Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA
  • 2Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 84, Iss. 3 — September 2011

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
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
×