Partitioning and modularity of graphs with arbitrary degree distribution

Abstract

We solve the graph bi-partitioning problem in dense graphs with arbitrary degree distribution using the replica method. We find the cut-size to scale universally with <k^1/2>. In contrast, earlier results studying the problem in graphs with a Poissonian degree distribution had found a scaling with <k>^1/2 [Fu and Anderson, J. Phys. A: Math. Gen. 19, 1986]. The new results also generalize to the problem of q-partitioning. They can be used to find the expected modularity Q [Newman and Grivan, Phys. Rev. E, 69, 2004] of random graphs and allow for the assessment of statistical significance of the output of community detection algorithms.

Revised version including new plots and improved discussion of some mathematical details

References in corpus (14)

• Finding and evaluating community structure in networks
• Error and attack tolerance of complex networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Functional cartography of complex metabolic networks
• Mixing patterns in networks
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Community analysis in social networks
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• When are networks truly modular?
• Spin Glass Phase Transition on Scale-Free Networks

Cited by in corpus (26)

• Community detection in graphs
• Community detection algorithms: a comparative analysis
• Finding statistically significant communities in networks
• Limits of modularity maximization in community detection
• The Statistical Physics of Real-World Networks
• Narrow scope for resolution-limit-free community detection
• Robustness of community structure in networks
• Community Detection via Maximization of Modularity and Its Variants
• Stochastic epidemics in a homogeneous community
• Statistical inference for epidemic processes in a homogeneous community (Part IV of the book Stochastic Epidemic Models and Inference)
• Stochastic epidemics in a heterogeneous community (Part III of the book Stochastic Epidemic Models and Inference)
• (Un)detectable cluster structure in sparse networks
• Resolving Structure in Human Brain Organization: Identifying Mesoscale Organization in Weighted Network Representations
• Finding and testing network communities by lumped Markov chains
• Limitation of multi-resolution methods in community detection
• Axioms for graph clustering quality functions
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Fast and accurate determination of modularity and its effect size
• Hierarchical clustering for graph visualization
• A statistical network analysis of the HIV/AIDS epidemics in Cuba
• Optimisation dans la détection de communautés recouvrantes et équilibre de Nash
• Validation of community robustness
• Ground state energy of $q$-state Potts model: the minimum modularity
• Overlapping Community Detection Optimization and Nash Equilibrium
• Modularity spectra, eigen-subspaces, and structure of weighted graphs
• Community Detection in Energy Networks based on Energy Self-Sufficiency and Dynamic Flexibility Activation