The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
From Louvain to Leiden: guaranteeing well-connected communities
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures










Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“When compared to six common clustering algorithms, including Leiden25 and CellHarmony26, VFC was the top performing algorithm on every simulation on the T cell data and best performing, on average, on the zebrafish dataset, with a 57% increase in average performance over Louvain, which was the next best algorithm”
From Quantifying the effect of experimental perturbations at single-cell resolution (2021) · cites this paper as [25]
The cited source says what the claim attributes to it.
In the citing paper
“Louvain’s successor Leiden circumvents this issue by yielding guaranteed connected communities and is computationally more efficient52.”
From Best practices for single-cell analysis across modalities (2023) · cites this paper as [52]
The cited source says what the claim attributes to it.
In the citing paper
“However, the Louvain algorithm can lead to arbitrarily poorly connected communities52.”
From Best practices for single-cell analysis across modalities (2023) · cites this paper as [52]
The cited source says what the claim attributes to it.
In the citing paper
“We found that many t-types had total variance substantially above the variances of the k-means clusters (Fig. 5b) and an alternative analysis using entropies of Leiden clustering35 often highlighted the same t-types as variable (Extended Data Fig. 8).”
From Phenotypic variation of transcriptomic cell types in mouse motor cortex (2021) · cites this paper as [35]
The cited source says what the claim attributes to it.
In the citing paper
“Community detection uses the Leiden algorithm [28] with ModularityVertexPartition, producing hierarchical subclustering to depth 3.”
From SuperLocalMemory: Privacy-Preserving Multi-Agent Memory with Bayesian Trust Defense Against Memory Poisoning (2026) · cites this paper as [28]
5 more claims about this paper
Create a free account to see every claim other papers make about this one.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424 · cited 3×
“The Louvain algorithm 10 is very simple and elegant.”
MethodFinding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931 · cited 2×
“The Leiden algorithm consists of three phases: (1) local moving of nodes, (2) refinement of the partition and (3) aggregation of the network based on the refined partition, using the non-refined partition to create an initial partition for the aggregate network.”
BackgroundMethodComplex brain networks: graph theoretical analysis of structural and functional systems
Bullmore, E., & Sporns, O. (2009) · Nature Reviews Neuroscience · doi:10.1038/nrn2575 · Cited by 11,820
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · cited 4×
“The Leiden algorithm consists of three phases: (1) local moving of nodes, (2) refinement of the partition and (3) aggregation of the network based on the refined partition, using the non-refined partition to create an initial partition for the aggregate network.”
BackgroundMethodInfluentialFinding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390 · cited 1×
“Optimising modularity is NP-hard 5 , and consequentially many heuristic algorithms have been proposed, such as hierarchical agglomeration 6 , extremal optimisation 7 , simulated annealing 4,8 and spectral 9 algorithms.”
MethodFinding community structure in networks using the eigenvectors of matrices
Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.74.036104 · Cited by 4,761
Functional cartography of complex metabolic networks
Guimerà, R., & Nunes Amaral, L. A. (2005) · Nature · doi:10.1038/nature03288 · Cited by 3,983 · cited 2×
“Optimising modularity is NP-hard 5 , and consequentially many heuristic algorithms have been proposed, such as hierarchical agglomeration 6 , extremal optimisation 7 , simulated annealing 4,8 and spectral 9 algorithms.”
MethodNear linear time algorithm to detect community structures in large-scale networks
Raghavan, U. N., Albert, R., & Kumara, S. (2007) · Physical Review E · doi:10.1103/physreve.76.036106 · Cited by 3,502 · cited 2×
“Trying to fix the problem by simply considering the connected components of communities 19–21 is unsatisfactory because it addresses only the most extreme case and does not resolve the more fundamental problem.”
BackgroundBenchmark graphs for testing community detection algorithms
Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008) · Physical Review E · doi:10.1103/physreve.78.046110 · Cited by 3,051 · cited 1×
“To study the scaling of the Louvain and the Leiden algorithm, we rely on a variant of a well-known approach for constructing benchmark networks 28 .”
MethodResolution limit in community detection
Fortunato, S., & Barthélemy, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0605965104 · Cited by 3,024 · cited 2×
“The algorithm may yield arbitrarily badly connected communities, over and above the well-known issue of the resolution limit 14 .”
Background
Research works printed but not linked: 2
- Porter, M. A., Onnela, J.-P. & Mucha, P. J. Communities in Networks. Not. AMS 56, 1082–1097 (2009).
- Luecken, M. D. Application of multi-resolution partitioning of interaction networks to the study of complex disease. Ph.D. thesis, (University of Oxford, 2016).
Cited by
Spatiotemporal transcriptomic atlas of mouse organogenesis using DNA nanoball-patterned arrays
Chen, A., Liao, S., Cheng, M., Ma, K., Wu, L., Lai, Y., Qiu, X., Yang, J., Xu, J., Hao, S., et al. (2022) · Cell · doi:10.1016/j.cell.2022.04.003 · Cited by 1,784
Cells of the adult human heart
Litviňuková, M., Talavera-López, C., Maatz, H., Reichart, D., Worth, C. L., Lindberg, E. L., Kanda, M., Polanski, K., Heinig, M., Lee, M., et al. (2020) · Nature · doi:10.1038/s41586-020-2797-4 · Cited by 1,729
Landscape and Dynamics of Single Immune Cells in Hepatocellular Carcinoma
Zhang, Q., He, Y., Luo, N., Patel, S. J., Han, Y., Gao, R., Modak, M., Carotta, S., Haslinger, C., Kind, D., et al. (2019) · Cell · doi:10.1016/j.cell.2019.10.003 · Cited by 1,624
scGPT: Towards Building a Foundation Model for Single-Cell Multi-omics Using Generative AI
Cui, H., Wang, C., Maan, H., Pang, K., Luo, F., & Wang, B. (2023) · doi:10.1101/2023.04.30.538439 · Cited by 1,694
Cellpose 2.0: how to train your own model
Pachitariu, M., & Stringer, C. (2022) · Nature Methods · doi:10.1038/s41592-022-01663-4 · Cited by 1,381
“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].”
MethodInfluential
Metadata
- Authors
- Traag, V. A., Waltman, L., & van Eck, N. J.
- Affiliations
- Leiden University (NL)
- Corresponding author
- Traag, V. A.
- Venue
- Scientific Reports
- Published
- 2019-03-26
- Volume
- 9
- Issue
- 1
- Pages
- 5233-5233
- ISSN
- 2045-2322 (ISSN-L)
- PMC
- PMC6435756
- OpenAlex
- W2897249806
- Cited by
- 5,635
- References
- 27
- Citations by year
- 2026: 1250 · 2025: 1281 · 2024: 980 · 2023: 757 · 2022: 639 · 2021: 466 · 2020: 213 · 2019: 46
- FWCI
- 158.78
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
- Locations
- Scientific Reports (publishedVersion, cc-by)
- Europe PMC (PubMed Central) (publishedVersion, other-oa)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Leiden Repository (Leiden University) (submittedVersion, cc-by)
- Data Archiving and Networked Services (DANS) (submittedVersion, cc-by)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- Leiden Repository (Leiden University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Bioinformatics and Genomic Networks
- Keywords
- community detection, Louvain algorithm, Leiden algorithm, network partitioning, community connectivity, complex networks
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: From Louvain to Leiden: guaranteeing well-connected communities. https://app.cochat.ai/papers/10.1038/s41598-019-41695-z
- The paper
- Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports. https://doi.org/10.1038/s41598-019-41695-z
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.