Loops and multiple edges in modularity maximization of networks.

Area of Science:

• Network science
• Graph theory
• Statistical physics

Background:

• The Newman-Girvan modularity maximization model is a standard for community detection in networks.
• Existing models often assume simple graphs, neglecting loops and multiple edges common in general graphs.
• Null models are crucial for evaluating the significance of detected communities by randomizing network structures while preserving properties like degree distribution.

Purpose of the Study:

• To develop and validate modified null models for network community detection that explicitly handle graphs with loops and multiple edges.
• To provide algebraic methods for constructing these null models, moving beyond simulation-based approaches.
• To analyze the impact of loops and multiple edges on modularity calculations.

Main Methods:

• Derivation of sharp bounds on the expected number of loops in random graphs with preserved degree distributions.
• Algebraic construction of modified null models for graphs with specific combinations of loops and multiple edges (e.g., no loops but multiple edges, loops but no multiple edges, neither loops nor multiple edges).
• Validation of the proposed null models using the exact clique partitioning algorithm by Grötschel and Wakabayashi.

Main Results:

• Quantification of the expected number of loops and their influence on modularity in standard null models.
• Introduction of novel, algebraically derived null models tailored for different graph types (simple, multigraphs, pseudographs).
• Demonstration that the proposed null models provide a more accurate baseline for community detection compared to traditional models when dealing with non-simple graphs.

Conclusions:

• Modified null models are essential for accurate community detection in networks that deviate from simple graph assumptions.
• The algebraic approach offers a robust and efficient alternative to simulation for constructing these null models.
• This work enhances the robustness and applicability of modularity-based community detection across diverse network structures.