From Louvain to Leiden: guaranteeing well-connected communities

Area of Science:

• Network science
• Computer science
• Data analysis

Background:

• Community detection is crucial for understanding complex networks.
• The Louvain algorithm is a popular but flawed method for community detection.
• Existing methods struggle with generating well-connected communities.

Purpose of the Study:

• To identify and address the limitations of the Louvain algorithm.
• To introduce a novel algorithm, the Leiden algorithm, for improved community detection.
• To provide theoretical guarantees for community connectivity and convergence.

Main Methods:

• Analysis of the Louvain algorithm's defect leading to disconnected communities.
• Development and theoretical proof of the Leiden algorithm's properties.
• Experimental evaluation on benchmark and real-world networks comparing Leiden and Louvain.

Main Results:

• The Louvain algorithm can produce badly connected (up to 25%) and disconnected (up to 16%) communities.
• The Leiden algorithm guarantees connected communities.
• The Leiden algorithm demonstrates faster performance and superior partition quality compared to Louvain.

Conclusions:

• The Leiden algorithm offers a significant improvement over the Louvain algorithm for network community detection.
• Guaranteed connectivity and improved efficiency make Leiden a valuable tool for network analysis.
• The Leiden algorithm provides a robust and reliable method for uncovering community structures.