Cited by 21,424Complex Network Analysis TechniquesAdvanced Clustering Algorithms ResearchBioinformatics and Genomic Networks

Fast unfolding of communities in large networks

Open access
Blondel, Vincent D, Guillaume, Jean-Loup, Lambiotte, Renaud, Lefebvre, Etienne·2008·Journal of Statistical Mechanics: Theory and Experiment

Abstract

We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection methods in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2 million customers and by analysing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad hoc modular networks.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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

Integrity signals

Registry

Crossref · 10.1088/1742-5468/2008/10/p10008

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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?

  • Both the Louvain and Leiden algorithms identify Kumārajīva and his students as a community distinct from Dao'an and Huiyuan.

    “Both the Louvain (Blondel et al. 2008) and the Leiden algorithm (Traag, Waltman, and van Eck 2018) can identify Kumārajīva and his students as a community distinct from that of Dao'an and Huiyuan (fig.2-1).”
  • Kalehbasti et al. proposed replacing the greedy heuristic within the Louvain algorithm by a QUBO solver to consider a larger search space in each iteration.

    “Kalehbasti et al.[74] proposed the generalizable idea of replacing the greedy heuristic within the Louvain algorithm [165], a classical heuristic for the k-community detection problem, by a QUBO solver to consider a larger search space in each iteration [74].”
  • Unsupervised clustering by Louvain algorithm and UMAP produced 38 distinct cell clusters.

    “Unsupervised clustering by the Louvain algorithm60 and visualization by uniform manifold approximation and projection (UMAP) produced 38 distinct cell clusters”
  • There has been an influx of algorithms that seek to improve upon the traditionally used community detection ones.

    “Along with this growth there has been an influx of algorithms that seek to improve upon the traditionally used ones (e.g., [53]).”
  • After PhenoGraph, the standard approach to clustering single-cell datasets has become multi-resolution modularity optimization as implemented in the Louvain algorithm on single-cell KNN graphs.

    “After the pioneering PhenoGraph method (Levine et al, 2015), the standard approach to clustering single‐cell datasets has become multi‐resolution modularity optimization (Newman & Girvan, 2004; Reichardt & Bornholdt, 2006) as implemented in the Louvain algorithm (Blondel et al, 2008) on single‐cell KNN graphs.”

    From Current best practices in single-cell RNA-seq analysis: a tutorial (2019) · cites this paper as Blondel et al, 2008

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 29

  1. Albert R and Barabási A-L, 2002 Rev. Mod. Phys. 74 4797 · DOI · Paper page
  2. Newman M E J, Barabási A-L and Watts D J, 2006 The Structure and Dynamics of Networks (Princeton, NJ: Princeton University Press)
  3. Fortunato S and Castellano C, 2007 arXiv:0712.2716 · arXiv
  4. Girvan M and Newman M E J, 2002 Proc. Nat. Acad. Sci. 99 7821 · DOI · Paper page
  5. Radicchi F, Castellano C, Cecconi F, Loreto V and Parisi D, 2004 Proc. Nat. Acad. Sci. 101 2658 · DOI · Paper page
  6. Clauset A, Newman M E J and Moore C, 2004 Phys. Rev. E 70 066111 · DOI · Paper page
  7. Wu F and Huberman B A, 2004 Eur. Phys. J. B 38 331 · DOI
  8. Newman M E J, 2006 Phys. Rev. E 74 036104 · DOI
  9. Newman M E J, 2004 Phys. Rev. E 70 056131 · DOI
  10. Newman M E J, 2004 Phys. Rev. E 69 066133 · DOI
  11. Brandes U, Delling D, Gaertler M, Goerke R, Hoefer M, Nikoloski Z and Wagner D, 2006 arXiv:physics/0608255 · arXiv
  12. Guimera R, Sales M and Amaral L A N, 2004 Phys. Rev. E 70 025101 · DOI · Paper page
  13. Wakita K and Tsurumi T, 2007 Proc. IADIS Int. Conf. on WWW/Internet 2007 p 153
  14. Palla G, Derényi I, Farkas I and Vicsek T, 2005 Nature 435 814 · DOI · Paper page
  15. Raghavan U N, Albert R and Kumara S, 2007 Phys. Rev. E 76 036106 · DOI
  16. Sales-Pardo M, Guimera R, Moreira A A and Amaral L A N, 2007 Proc. Nat. Acad. Sci. 104 15224 · DOI
  17. Arenas A, Duch J, Fernández A and Gómez S, 2007 New J. Phys. 9 176 · DOI
  18. Song C, Havlin S and Makse H A, 2005 Nature 433 392 · DOI · Paper page
  19. Hoerdt M and Magoni D, 2003 Proc. 11th Int. Conf. on Software, Telecommunications and Computer Networks p 257
  20. Albert R, Jeong H and Barabási A-L, 1999 Nature 401 130 · DOI
  21. Danon L, Díaz-Guilera A, Duch J and Arenas A, 2005 J. Stat. Mech. P09008 · DOI
  22. Reichardt J and Bornholdt S, 2004 Phys. Rev. Lett. 93 218701 · DOI
  23. Duch J and Arenas A, 2005 Phys. Rev. E 72 027104 · DOI
  24. Lancichinetti A, Fortunato S and Kertesz J, 2008 arXiv:0802.1218 · arXiv
  25. Lambiotte R, Blondel V D, de Kerchove C, Huens E, Prieur C, Smoreda Z and Van Dooren P, 2008 Physica A 387 5317 · DOI
  26. Palla G, Barabási A-L and Vicsek T, 2007 Nature 446 664 · DOI
  27. Onnela J-P, Saramäki J, Hyvönen J, Szabó G, Lazer D, Kaski K, Kertész J and Barabási A-L, 2007 Proc. Nat. Acad. Sci. 104 7332 · DOI
  28. Lambiotte R, Ausloos M and Ho lyst J A, 2007 Phys. Rev. E 75 030101(R) · DOI
  29. Arenas A, Fernández A and Gómez S, 2008 New J. Phys. 10 053039 · DOI

Cited by

Sorted by citations

Authors
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E.
Affiliations
  • UCLouvain (BE)
  • LIP6 (FR)
  • Imperial College London (GB)
Venue
Journal of Statistical Mechanics: Theory and Experiment
Published
2008-10-01
Volume
2008
Issue
10
Pages
P10008
ISSN
1742-5468 (ISSN-L)
OpenAlex
W2131681506
Cited by
21,424
References
3
Citations by year
2026: 1670 · 2025: 1998 · 2024: 2038 · 2023: 1890 · 2022: 1955 · 2021: 2137 · 2020: 1821 · 2019: 1612 · 2018: 1411 · 2017: 1122 · 2016: 1014 · 2015: 837 · 2014: 716 · 2013: 526 · 2012: 314
FWCI
90.28
Type
journal article
Language
en
Open access
Locations
  • Journal of Statistical Mechanics Theory and Experiment (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Repository of the University of Namur (submittedVersion, other-oa)
  • HAL (submittedVersion)
  • Digital Access to Libraries (Université catholique de Louvain (UCL), l'Université de Namur (UNamur) and the Université Saint-Louis (USL-B)) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Agence Nationale de la Recherche
  • Fédération Wallonie-Bruxelles
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, modularity optimization, large-scale networks, mobile phone networks, language communities, web graph, modular networks, computational efficiency

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