Detectability of communities in heterogeneous networks

Area of Science:

• Network Science
• Statistical Physics
• Data Analysis

Background:

• Communities are key to understanding network structures.
• Modularity optimization is the standard method for community detection.
• Conditions for successful community detection via modularity remain unclear.

Purpose of the Study:

• To develop a theory for conditions enabling community detection.
• To investigate the role of degree distribution heterogeneity.
• To assess detectability in various network models, including scale-free networks.

Main Methods:

• Theoretical framework development for community detection conditions.
• Application of the theory to diverse network models.
• Analysis of modularity maximization performance.

Main Results:

• Heterogeneity in degree distribution enhances community recovery.
• Modularity successfully detects communities in scale-free networks (γ<2.5).
• A theory was established to define detectability conditions.

Conclusions:

• Degree distribution heterogeneity is vital for robust community detection.
• Modularity maximization is reliable for scale-free networks under specific conditions.
• The developed theory provides a basis for understanding community detection limits.