From Louvain to Leiden: guaranteeing well-connected communities
Open Access
- 26 March 2019
- journal article
- research article
- Published by Springer Science and Business Media LLC in Scientific Reports
- Vol. 9 (1), 1-12
- https://doi.org/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.Keywords
This publication has 25 references indexed in Scilit:
- A new methodology for constructing a publication‐level classification system of scienceJournal of the American Society for Information Science and Technology, 2012
- Community detection in graphsPhysics Reports, 2009
- Complex brain networks: graph theoretical analysis of structural and functional systemsNature Reviews Neuroscience, 2009
- Benchmark graphs for testing community detection algorithmsPhysical Review E, 2008
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Resolution limit in community detectionProceedings of the National Academy of Sciences of the United States of America, 2007
- Finding community structure in networks using the eigenvectors of matricesPhysical Review E, 2006
- Community detection in complex networks using extremal optimizationPhysical Review E, 2005
- Functional cartography of complex metabolic networksNature, 2005
- Finding community structure in very large networksPhysical Review E, 2004