Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

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 access
Traag, V. A., Waltman, L., van Eck, N. J. · 2019 · Scientific Reports

Abstract

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/s41598-019-41695-z

Cites

30 of 30 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1 Louvain algorithm. The Louvain algorithm starts from a singleton partition in which each node is in its own community (a). The algorithm moves individual nodes from one community to another to find a partition (b). Based on this partition, an aggregate network is created (c). The algorithm then moves individual nodes in the aggregate network (d). These steps are repeated until the quality cannot be increased further.
Figure 1 Louvain algorithm. The Louvain algorithm starts from a singleton partition in which each node is in its own community (a). The algorithm moves individual nodes from one community to another to find a partition (b). Based on this partition, an aggregate network is created (c). The algorithm then moves individual nodes in the aggregate network (d). These steps are repeated until the quality cannot be increased further.CC BY · PubMed Central
Figure 2 Disconnected community. Consider the partition shown in (a). When node 0 is moved to a different community, the red community becomes internally disconnected, as shown in (b). However, nodes 1–6 are still locally optimally assigned, and therefore these nodes will stay in the red community.
Figure 2 Disconnected community. Consider the partition shown in (a). When node 0 is moved to a different community, the red community becomes internally disconnected, as shown in (b). However, nodes 1–6 are still locally optimally assigned, and therefore these nodes will stay in the red community.CC BY · PubMed Central
Figure 3 Leiden algorithm. The Leiden algorithm starts from a singleton partition (a). The algorithm moves individual nodes from one community to another to find a partition (b), which is then refined (c). An aggregate network (d) is created based on the refined partition, using the non-refined partition to create an initial partition for the aggregate network. For example, the red community in (b) is refined into two subcommunities in (c), which after aggregation become two separate nodes in (d), both belonging to the same community. The algorithm then moves individual nodes in the aggregate network (e). In this case, refinement does not change the partition (f). These steps are repeated until no further improvements can be made.
Figure 3 Leiden algorithm. The Leiden algorithm starts from a singleton partition (a). The algorithm moves individual nodes from one community to another to find a partition (b), which is then refined (c). An aggregate network (d) is created based on the refined partition, using the non-refined partition to create an initial partition for the aggregate network. For example, the red community in (b) is refined into two subcommunities in (c), which after aggregation become two separate nodes in (d), both belonging to the same community. The algorithm then moves individual nodes in the aggregate network (e). In this case, refinement does not change the partition (f). These steps are repeated until no further improvements can be made.CC BY · PubMed Central
Figure 4 Badly connected communities. Percentage of communities found by the Louvain algorithm that are either disconnected or badly connected compared to percentage of badly connected communities found by the Leiden algorithm. Note that communities found by the Leiden algorithm are guaranteed to be connected.
Figure 4 Badly connected communities. Percentage of communities found by the Louvain algorithm that are either disconnected or badly connected compared to percentage of badly connected communities found by the Leiden algorithm. Note that communities found by the Leiden algorithm are guaranteed to be connected.CC BY · PubMed Central
Figure 5 Scaling of benchmark results for network size. Speed and quality of the Louvain and the Leiden algorithm for benchmark networks of increasing size (two iterations). For larger networks and higher values of μ, Louvain is much slower than Leiden. For higher values of μ, Leiden finds better partitions than Louvain.
Figure 5 Scaling of benchmark results for network size. Speed and quality of the Louvain and the Leiden algorithm for benchmark networks of increasing size (two iterations). For larger networks and higher values of μ, Louvain is much slower than Leiden. For higher values of μ, Leiden finds better partitions than Louvain.CC BY · PubMed Central
Figure 6 Runtime versus quality for benchmark networks. Speed and quality for the first 10 iterations of the Louvain and the Leiden algorithm for benchmark networks (n = 106 and n = 107). The horizontal axis indicates the cumulative time taken to obtain the quality indicated on the vertical axis. Each point corresponds to a certain iteration of an algorithm, with results averaged over 10 experiments. In general, Leiden is both faster than Louvain and finds better partitions.
Figure 6 Runtime versus quality for benchmark networks. Speed and quality for the first 10 iterations of the Louvain and the Leiden algorithm for benchmark networks (n = 106 and n = 107). The horizontal axis indicates the cumulative time taken to obtain the quality indicated on the vertical axis. Each point corresponds to a certain iteration of an algorithm, with results averaged over 10 experiments. In general, Leiden is both faster than Louvain and finds better partitions.CC BY · PubMed Central
Figure 7 Scaling of benchmark results for difficulty of the partition. Speed of the first iteration of the Louvain and the Leiden algorithm for benchmark networks with increasingly difficult partitions (n = 107). In the most difficult case (μ = 0.9), Louvain requires almost 2.5 days, while Leiden needs fewer than 10 minutes.
Figure 7 Scaling of benchmark results for difficulty of the partition. Speed of the first iteration of the Louvain and the Leiden algorithm for benchmark networks with increasingly difficult partitions (n = 107). In the most difficult case (μ = 0.9), Louvain requires almost 2.5 days, while Leiden needs fewer than 10 minutes.CC BY · PubMed Central
Figure 8 First iteration runtime for empirical networks. Speed of the first iteration of the Louvain and the Leiden algorithm for six empirical networks. Leiden is faster than Louvain especially for larger networks.
Figure 8 First iteration runtime for empirical networks. Speed of the first iteration of the Louvain and the Leiden algorithm for six empirical networks. Leiden is faster than Louvain especially for larger networks.CC BY · PubMed Central
Figure 9 Runtime versus quality for empirical networks. Speed and quality for the first 10 iterations of the Louvain and the Leiden algorithm for six empirical networks. The horizontal axis indicates the cumulative time taken to obtain the quality indicated on the vertical axis. Each point corresponds to a certain iteration of an algorithm, with results averaged over 10 experiments. Leiden is both faster than Louvain and finds better partitions.
Figure 9 Runtime versus quality for empirical networks. Speed and quality for the first 10 iterations of the Louvain and the Leiden algorithm for six empirical networks. The horizontal axis indicates the cumulative time taken to obtain the quality indicated on the vertical axis. Each point corresponds to a certain iteration of an algorithm, with results averaged over 10 experiments. Leiden is both faster than Louvain and finds better partitions.CC BY · PubMed Central
Figure 10 Number of iterations until stability. Number of iterations before the Leiden algorithm has reached a stable iteration for six empirical networks. In a stable iteration, the partition is guaranteed to be node optimal and subpartition γ-dense.
Figure 10 Number of iterations until stability. Number of iterations before the Leiden algorithm has reached a stable iteration for six empirical networks. In a stable iteration, the partition is guaranteed to be node optimal and subpartition γ-dense.CC BY · PubMed Central

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.

A few free checks a day · papers already verified open instantly · results are public

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?

5 more claims about this paper

Create a free account to see every claim other papers make about this one.

See all claims — free account

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

Show all 27 references

Research works printed but not linked: 2

  1. Porter, M. A., Onnela, J.-P. & Mucha, P. J. Communities in Networks. Not. AMS 56, 1082–1097 (2009).
  2. 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

See all 5,635

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)
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
Licence
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.