Partitioning and modularity of graphs with arbitrary degree distribution

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 square root [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.