Partitioning and modularity of graphs with arbitrary degree distribution.

By J. Reichardt, Stefan Bornholdt. 2006

92 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Condensed Matter Physics, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Condensed Matter Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in graphs (2009, methodology): “The general spin glass framework by Reichardt and Bornholdt ((Reichardt and Bornholdt, 2006a) and Section VI.”
Inferring spatial and signaling relationships between cells from single cell transcriptomic data (2020, methodology): “A python implementation [23] of louvain clustering algorithm [2] with the RBConfiguration method [18] is used to cluster the genes based on a neighborhood graph built with the quantified spatial pattern differences.”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “In part as a response to this, some recent work has had a more statistical flavor [86, 140, 144, 94, 133].”
Community Structure in Graphs (2007, background): “Random graphs can also have partitions with large modularity values, even though clusters are not explicitly built in [31, 56].”
Finding Statistically Significant Communities in Networks (2010, unknown): “However, modularity is based on the expected value of variables estimated on the null model, neglecting random fluctuations, which is why modularity can attain large values on specific partitions of random graphs [65–67].”
The statistical physics of real-world networks (2018, unknown): “[66] J.”
Statistical properties of community structure in large social and information networks (2008, background): “In part as a response to this, some recent work has had a more statistical flavor [85, 137, 141, 93, 130].”