Bayan algorithm: Detecting communities in networks through exact and approximate optimization of modularity.

Area of Science:

• Network Science
• Computer Science
• Data Mining

Background:

• Community detection is crucial in network analysis, with modularity maximization being a common but often suboptimal approach.
• Existing methods struggle to find globally optimal partitions, leaving this area underexplored.
• The need for accurate and stable community detection algorithms is critical across various scientific fields.

Purpose of the Study:

• To introduce and evaluate the Bayan algorithm for network community detection.
• To compare Bayan's performance against 30 existing methods, focusing on optimality and approximation guarantees.
• To demonstrate the superiority of maximum-modularity partitions in retrieving planted structures.

Main Methods:

• Developed the Bayan algorithm, which guarantees global modularity maximization or approximation.
• Compared Bayan with 30 community detection algorithms on diverse, structurally varied networks using standard benchmarks.
• Evaluated partitions based on metrics including description length, coverage, performance, average conductance, and well-clusteredness.

Main Results:

• Maximum-modularity partitions generated by Bayan showed distinctive accuracy and stability in retrieving planted partitions.
• Bayan's partitions outperformed 29 other algorithms across multiple performance metrics.
• Bayan achieves optimality or near-optimality efficiently, outperforming commercial and open-source solvers for modularity maximization.

Conclusions:

• The Bayan algorithm is a reliable and accurate method for community detection in small networks.
• Maximum-modularity partitions offer significant advantages over heuristic approaches.
• The availability of the 'bayanpy' Python implementation facilitates broader adoption and research.