skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

From Louvain to Leiden: guaranteeing well-connected communities

Scientific reports, 2019-03, Vol.9 (1), p.5233-5233, Article 5233 [Peer Reviewed Journal]

This work is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License. ;The Author(s) 2019 ;ISSN: 2045-2322 ;EISSN: 2045-2322 ;DOI: 10.1038/s41598-019-41695-z ;PMID: 30914743

Full text available

Citations Cited by
  • Title:
    From Louvain to Leiden: guaranteeing well-connected communities
  • Author: Traag, V A ; Waltman, L ; van Eck, N J
  • Subjects: Algorithms ; Community structure
  • Is Part Of: Scientific reports, 2019-03, Vol.9 (1), p.5233-5233, Article 5233
  • Description: 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.
  • Publisher: England: Nature Publishing Group
  • Language: English
  • Identifier: ISSN: 2045-2322
    EISSN: 2045-2322
    DOI: 10.1038/s41598-019-41695-z
    PMID: 30914743
  • Source: PubMed Central
    DOAJ: Directory of Open Access Journals
    ProQuest Central
Back to results list
Go to Previous pagePrevious Result  10 NextGo to Next page
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait