Partitioning and modularity of graphs with arbitrary degree distribution.

Area of Science:

• Statistical physics
• Network science
• Graph theory

Background:

• The graph bipartitioning problem is crucial for network analysis.
• Previous studies focused on specific degree distributions, limiting generalizability.
• Understanding community structure in complex networks remains a challenge.

Purpose of the Study:

• To solve the graph bipartitioning problem in dense graphs with arbitrary degree distributions.
• To establish a universal scaling law for the cut size.
• To generalize findings to q-partitioning and assess community detection algorithms.

Main Methods:

• Application of the replica method from statistical physics.
• Analysis of dense graphs with arbitrary degree distributions.
• Generalization to q-partitioning problems.

Main Results:

• The cut size in dense graphs universally scales with the square root of the average degree ().
• This contrasts with previous findings for Poissonian degree distributions ().
• The method generalizes to q-partitioning and aids in calculating expected modularity (Q).

Conclusions:

• The replica method provides a universal solution for graph bipartitioning in dense graphs.
• The derived scaling law advances the understanding of network community structure.
• This work offers a tool for evaluating the statistical significance of community detection algorithms.