Skip to content
naulon
Get started

No retraction, correction or concern found when last checked on Oct 15, 2026.

From Louvain to Leiden: guaranteeing well-connected communities

V. A. Traag, L. Waltman, N. J. van Eck

Scientific Reports · 2019 · CC BY

doi:10.1038/s41598-019-41695-z

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.

Full text

Its licence does not allow us to show the full text. Read it at PubMed Central:

Read at PubMed Central

References 29

  1. 1.

    Fortunato S. Community detection in graphs. Phys. Rep. 2010;486:75-174.

    Not in our library10.1016/j.physrep.2009.11.002

  2. 2.

    Porter MA, Onnela J-P, Mucha PJ. Communities in Networks. Not. AMS. 2009;56:1082-1097.

    Not in our library

  3. 3.

    Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Phys. Rev. E. 2004;69:026113.

    Not in our library10.1103/physreve.69.026113

  4. 4.

    Reichardt J, Bornholdt S. Statistical mechanics of community detection. Phys. Rev. E. 2006;74:016110.

    Not in our library10.1103/physreve.74.016110

  5. 5.

    Brandes U, et al. On Modularity Clustering. IEEE Trans. Knowl. Data Eng. 2008;20:172-188.

    Not in our library10.1109/tkde.2007.190689

  6. 6.

    Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks. Phys. Rev. E. 2004;70:066111.

    Not in our library10.1103/physreve.70.066111

  7. 7.

    Duch J, Arenas A. Community detection in complex networks using extremal optimization. Phys. Rev. E. 2005;72:027104.

    Not in our library10.1103/physreve.72.027104

  8. 8.

    Guimerà R, Nunes Amaral LA. Functional cartography of complex metabolic networks. Nature. 2005;433:895-900.

    Not in our library10.1038/nature03288

  9. 9.

    Newman MEJ. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E. 2006;74:036104.

    Not in our library10.1103/physreve.74.036104

  10. 10.

    Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 2008;10008:6.

    Not in our library10.1088/1742-5468/2008/10/p10008

  11. 11.

    Lancichinetti A, Fortunato S. Community detection algorithms: A comparative analysis. Phys. Rev. E. 2009;80:056117.

    Not in our library10.1103/physreve.80.056117

  12. 12.
    A Comparative Analysis of Community Detection Algorithms on Artificial Networks · 2016
    Corrected
  13. 13.

    Traag VA, Van Dooren P, Nesterov Y. Narrow scope for resolution-limit-free community detection. Phys. Rev. E. 2011;84:016114.

    Not in our library10.1103/physreve.84.016114

  14. 14.

    Fortunato S, Barthélemy M. Resolution Limit in Community Detection. Proc. Natl. Acad. Sci. USA. 2007;104:36.

    Not in our library10.1073/pnas.0605965104

  15. 15.

    Waltman L, van Eck NJ. A smart local moving algorithm for large-scale modularity-based community detection. Eur. Phys. J. B. 2013;86:471.

    Not in our library10.1140/epjb/e2013-40829-0

  16. 16.

    Ozaki N, Tezuka H, Inaba M. A Simple Acceleration Method for the Louvain Algorithm. Int. J. Comput. Electr. Eng. 2016;8:207-218.

    Not in our library10.17706/ijcee.2016.8.3.207-218

  17. 17.

    Bae S, Halperin D, West JD, Rosvall M, Howe B. Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis. ACM Trans. Knowl. Discov. Data. 2017;11:1-30.

    Not in our library10.1145/2992785

  18. 18.

    Traag VA. Faster unfolding of communities: Speeding up the Louvain algorithm. Phys. Rev. E. 2015;92:032801.

    Not in our library10.1103/physreve.92.032801

  19. 19.

    Luecken, M. D. Application of multi-resolution partitioning of interaction networks to the study of complex disease. Ph.D. thesis, (University of Oxford, 2016).

    Not in our library

  20. 20.
    PAGA: graph abstraction reconciles clustering with trajectory inference through a topology preserving map of single cells · 2019
    No notice
  21. 21.

    Raghavan U, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E. 2007;76:036106.

    Not in our library10.1103/physreve.76.036106

  22. 22.

    Rotta R, Noack A. Multilevel local search algorithms for modularity clustering. J. Exp. Algorithmics. 2011;16:2.1.

    Not in our library10.1145/1963190.1970376

  23. 23.

    Traag, V. A., Waltman, L. & van Eck, N. J. networkanalysis. Zenodo, 10.5281/zenodo.1466831https://github.com/CWTSLeiden/networkanalysis. Source Code (2018).

    Not in our library

  24. 24.

    Traag, V. A. leidenalg 0.7.0. Zenodo, 10.5281/zenodo.1469357https://github.com/vtraag/leidenalg. Source Code (2018).

    Not in our library

  25. 25.

    Bullmore E, Sporns O. Complex brain networks: graph theoretical analysis of structural and functional systems. Nat. Rev. Neurosci. 2009;10:186-198.

    Not in our library10.1038/nrn2575

  26. 26.

    Waltman L, van Eck NJ. A new methodology for constructing a publication-level classification system of science. J. Am. Soc. Inf. Sci. Technol. 2012;63:2378-2392.

    Not in our library10.1002/asi.22748

  27. 27.

    Klavans R, Boyack KW. Which Type of Citation Analysis Generates the Most Accurate Taxonomy of Scientific and Technical Knowledge? J. Assoc. Inf. Sci. Technol. 2017;68:984-998.

    Not in our library10.1002/asi.23734

  28. 28.

    Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Phys. Rev. E. 2008;78:046110.

    Not in our library10.1103/physreve.78.046110

  29. 29.

    Good BH, De Montjoye YA, Clauset A. Performance of modularity maximization in practical contexts. Phys. Rev. E. 2010;81:046106.

    Not in our library10.1103/physreve.81.046106

Cited by papers we hold 91

and 71 more

Reads

Read by people on this page

None yet.

Checked or read by AI through naulon

None yet.

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.

Are you an author?

Is this your paper?

Claim it to add your note and be paid when agents cite it. Free.