From Louvain to Leiden: guaranteeing well-connected communities
By Vincent A. Traag, Ludo Waltman, Nees Jan van Eck. Scientific Reports, 2018
5,087 citations recorded by the source corpus.
Community detection is often used to understand the structure of large and complex networks. One of the most popular algorithms for uncovering community structure is the so-called Louvain algorithm. We show that this algorithm has a major defect that largely went unnoticed until now: the Louvain algorithm may yield arbitrarily badly connected communities. In the worst case, communities may even be disconnected, especially when running the algorithm iteratively. In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected. To address this problem, we introduce the Leiden algorithm. We prove that the Leiden algorithm yields communities that are guaranteed to be connected. In addition, we prove that, when the Leiden algorithm is applied iteratively, it converges to a partition in which all subsets of all communities are locally optimally assigned. Furthermore, by relying on a fast local move approach, the Leiden algorithm runs faster than the Louvain algorithm. We demonstrate the performance of the Leiden algorithm for several benchmark and real-world networks. We find that the Leiden algorithm is faster than the Louvain algorithm and uncovers better partitions, in addition to providing explicit guarantees.
Subfields: Artificial Intelligence, Computer Science Applications, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/79cdbabb22ef80074f5659430fe6fc97932798f5
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Bin Hu
- Levi Waldron
- Aaron T. L. Lun
- Zhangyang Gao
- Malte D. Luecken
- Cheng Tan
- Stan.Z.Li
- Christos J. Petropoulos
In Computer Science Applications
In Statistical and Nonlinear Physics
- Zhangyang Gao
- Malte D. Luecken
- Cheng Tan
- Stan.Z.Li
- C. Stringer
- Fabian J Theis
- Marius Pachitariu
- Vincent J. Carey
Citations in the corpus
- Cellpose 2.0: how to train your own model (2022, methodology): “We took the style vectors for all images and clustered them into nine different classes using the Leiden algorithm, illustrated on a t-SNE plot in Figure 2a [24, 25].”
- OpenCell: proteome-scale endogenous tagging enables the cartography of human cellular organization (2022, methodology): “For this, we first used an unsupervised Leiden clustering strategy commonly used to identify cell types in single-cell RNA sequencing datasets ( 55 ).”
- Identification of mobile genetic elements with geNomad (2023, positive): “To reduce taxonomic imbalance, we clustered TOPAZ genomes based on their amino acid identity (AAI) into 385 clusters using the Leiden algorithm 54 (as implemented in the igraph Python package, resolution parameter = 0.5) and picked the genome with the least contamination, as estimated by the…”
- Best practices for single-cell analysis across modalities (2023, methodology): “Alternatively, the cell-level view models cells individually using generalized mixed effect models, such as MAST 82 .”
- Giotto: a toolbox for integrative analysis and visualization of spatial expression data (2021, methodology): “Louvain and Leiden clustering [22] are implemented as doLouvainCluster and doLeidenCluster and can be directly applied on the created”
- Spike sorting with Kilosort4 (2024, neutral): “Well-known implementations of modularity optimization are the Leiden and Louvain algorithms 19,20 .”
- From Local to Global: A Graph RAG Approach to Query-Focused Summarization (2024, methodology): “The next step is to create report-like summaries of each community in the Leiden hierarchy, using a method designed to scale to very large datasets.”