Faster unfolding of communities: speeding up the Louvain algorithm.

Area of Science:

• Complex Networks
• Network Science
• Graph Theory

Background:

• Complex networks often display modular structures, identified by optimizing quality functions.
• Modularity optimization is a popular, though imperfect, method for community detection.
• The Louvain algorithm is a key method for optimizing modularity and analyzing network structures.

Purpose of the Study:

• To accelerate the Louvain algorithm for analyzing larger graphs more efficiently.
• To investigate the impact of moving nodes to random neighbor communities on runtime and quality.

Main Methods:

• Modification of the Louvain algorithm to consider random neighbor communities instead of the best.
• Theoretical analysis of runtime complexity reduction from O(m) to O(nlog〈k〉).
• Empirical evaluation on benchmark and real-world networks.

Main Results:

• The modified algorithm achieves 2-3 times speedup on benchmark networks and up to 10 times on real networks.
• Theoretical runtime complexity is reduced for networks with clear community structures.
• The performance gains are attributed to random neighbors being in good communities and likely being hubs.

Conclusions:

• The proposed simple modification offers a significant speedup for the Louvain algorithm, enhancing large-scale network analysis.
• A good quality-performance ratio is maintained, with only a slight decrease in quality, especially for modularity.
• The effectiveness of the speedup may vary for different community detection quality measures.