• Rapid Communication

Partitioning and modularity of graphs with arbitrary degree distribution

Jörg Reichardt and Stefan Bornholdt
Phys. Rev. E 76, 015102(R) – Published 10 July 2007

Abstract

We solve the graph bipartitioning problem in dense graphs with arbitrary degree distribution using the replica method. We find the cut size to scale universally with k. In contrast, earlier results studying the problem in graphs with a Poissonian degree distribution had found a scaling with k [Fu and Anderson, J. Phys. A 19, 1605 (1986)]. Our results also generalize to the problem of q partitioning. They can be used to find the expected modularity Q [Newman and Girvan, Phys. Rev. E 69, 026113 (2004)] of random graphs and allow for the assessment of the statistical significance of the output of community detection algorithms.

  • Figure
  • Figure
  • Figure
  • Received 12 June 2006

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

©2007 American Physical Society

Authors & Affiliations

Jörg Reichardt* and Stefan Bornholdt

  • Institute for Theoretical Physics, University of Bremen, D-28359 Bremen, Germany

  • *Present address: Institute for Theoretical Physics, University of Würzburg, Am Hubland, 97074 Würzburg, Germany.

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 76, Iss. 1 — July 2007

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
×