Faster unfolding of communities: Speeding up the Louvain algorithm
Open accessThe DOI matches its Crossref record; 10 of the 10 references it cites were found in a registry or an index.
Abstract
Many complex networks exhibit a modular structure of densely connected groups of nodes. Usually, such a modular structure is uncovered by the optimization of some quality function. Although flawed, modularity remains one of the most popular quality functions. The Louvain algorithm was originally developed for optimizing modularity, but has been applied to a variety of methods. As such, speeding up the Louvain algorithm enables the analysis of larger graphs in a shorter time for various methods. We here suggest to consider moving nodes to a random neighbor community, instead of the best neighbor community. Although incredibly simple, it reduces the theoretical runtime complexity from O(m) to O(nlog〈k〉) in networks with a clear community structure. In benchmark networks, it speeds up the algorithm roughly 2-3 times, while in some real networks it even reaches 10 times faster runtimes. This improvement is due to two factors: (1) a random neighbor is likely to be in a "good" community and (2) random neighbors are likely to be hubs, helping the convergence. Finally, the performance gain only slightly diminishes the quality, especially for modularity, thus providing a good quality-performance ratio. However, these gains are less pronounced, or even disappear, for some other measures such as significance or surprise.
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
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.
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
Finding 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
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Complex networks: structure and dynamics
BOCCALETTI, S., LATORA, V, MORENO, Y., CHAVEZ, M., & HWANG, D. (2006) · Physics Reports · doi:10.1016/j.physrep.2005.10.009 · Cited by 11,010
Finding 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
Hierarchical Organization of Modularity in Metabolic Networks
Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barabási, A.-L. (2002) · Science · doi:10.1126/science.1073374 · Cited by 4,224
Functional cartography of complex metabolic networks
Guimerà, R., & Nunes Amaral, L. A. (2005) · Nature · doi:10.1038/nature03288 · Cited by 3,983
Resolution 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
Statistical mechanics of community detection
Reichardt, J., & Bornholdt, S. (2006) · Physical Review E · doi:10.1103/physreve.74.016110 · Cited by 2,048
Stanley, R. P. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139058520 · Cited by 676
Origin of compartmentalization in food webs
Guimerà, R., Stouffer, D. B., Sales-Pardo, M., Leicht, E. A., Newman, M. E. J., & Amaral, L. A. N. (2010) · Ecology · doi:10.1890/09-1175.1 · Cited by 201
Cited by
From Louvain to Leiden: guaranteeing well-connected communities
Traag, V. A., Waltman, L., & van Eck, N. J. (2019) · Scientific Reports · doi:10.1038/s41598-019-41695-z · Cited by 5,635
“The new algorithm integrates several earlier improvements, incorporating a combination of smart local move 15 , fast local move 16,17 and random neighbour move 18 .”
BackgroundMethodSelf-citationThe microbiota regulate neuronal function and fear extinction learning
Chu, C., Murdock, M. H., Jing, D., Won, T. H., Chung, H., Kressel, A. M., Tsaava, T., Addorisio, M. E., Putzel, G. G., Zhou, L., et al. (2019) · Nature · doi:10.1038/s41586-019-1644-y · Cited by 421
Characterizing cis-regulatory elements using single-cell epigenomics
Preissl, S., Gaulton, K. J., & Ren, B. (2023) · Nature Reviews Genetics · doi:10.1038/s41576-022-00509-1 · Cited by 251
Nuclei multiplexing with barcoded antibodies for single-nucleus genomics
Gaublomme, J. T., Li, B., McCabe, C., Knecht, A., Yang, Y., Drokhlyansky, E., Van Wittenberghe, N., Waldman, J., Dionne, D., Nguyen, L., et al. (2019) · Nature Communications · doi:10.1038/s41467-019-10756-2 · Cited by 199
Kaiser, J., & Rauchfleisch, A. (2020) · Social Media + Society · doi:10.1177/2056305120969914 · Cited by 74
“, 2008) for directed graphs in Python (Traag, 2015) and visualized the networks with Gephi (nodes = channels, edges = recommendations).”
Method
Metadata
- Authors
- Traag, V. A.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2015-09-03
- Volume
- 92
- Issue
- 3
- Pages
- 032801-032801
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W1756737390
- Cited by
- 130
- References
- 10
- FWCI
- 2.35
- Type
- journal article
- Language
- en
- Open access
- green
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: Faster unfolding of communities: Speeding up the Louvain algorithm. https://app.cochat.ai/papers/10.1103/physreve.92.032801
- The paper
- Traag, V. A. (2015). Faster unfolding of communities: Speeding up the Louvain algorithm. Physical Review E. https://doi.org/10.1103/physreve.92.032801
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.