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 ⟨√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.