Fast algorithm for detecting community structure in networks

M. E. J. Newman
Phys. Rev. E 69, 066133 – Published 18 June 2004

Abstract

Many networks display community structure—groups of vertices within which connections are dense but between which they are sparser—and sensitive computer algorithms have in recent years been developed for detecting this structure. These algorithms, however, are computationally demanding, which limits their application to small networks. Here we describe an algorithm which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms. We give several example applications, including one to a collaboration network of more than 50 000 physicists.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 22 September 2003

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

©2004 American Physical Society

Authors & Affiliations

M. E. J. Newman

  • Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109-1120, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 69, Iss. 6 — June 2004

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
×