Scalable detection of statistically significant communities and hierarchies, using message passing for modularity

Area of Science:

• Network Science
• Statistical Physics
• Data Mining

Background:

• Modularity is a widely used metric for identifying community structure in complex networks.
• Maximizing modularity can result in unstable and unreliable community partitions, including spurious communities in random graphs.

Purpose of the Study:

• To develop a more robust method for community detection that overcomes the limitations of traditional modularity maximization.
• To identify consensus partitions and hierarchical structures in networks, even in the presence of noise or weak community signals.

Main Methods:

• The study treats modularity as a Hamiltonian in a finite-temperature system.
• An efficient belief propagation algorithm is employed to find the consensus of multiple high-modularity partitions.
• Recursive application of the algorithm is used to detect hierarchical community structures.

Main Results:

• The proposed algorithm successfully detects communities down to the detectability transition in stochastic block models.
• It identifies significant large communities in real-world networks where previous methods failed to find structure.
• Recursive application reveals hierarchical network structures more efficiently than existing techniques.

Conclusions:

• This novel approach provides a more reliable method for community detection in networks compared to standard modularity maximization.
• The algorithm effectively uncovers both broad community structures and fine-grained hierarchical organization in complex systems.
• It demonstrates superior performance on both synthetic and real-world network data.