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 . In contrast, earlier results studying the problem in graphs with a Poissonian degree distribution had found a scaling with [Fu and Anderson, J. Phys. A 19, 1605 (1986)]. Our results also generalize to the problem of partitioning. They can be used to find the expected modularity [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.
- Received 12 June 2006
DOI:https://doi.org/10.1103/PhysRevE.76.015102
©2007 American Physical Society