CoChat
Sign Up
Cited by 2,450Complex Network Analysis TechniquesBioinformatics and Genomic NetworksAdvanced Clustering Algorithms Research

Defining and identifying communities in networks

Open access
Radicchi, Filippo, Castellano, Claudio, Cecconi, Federico, Loreto, Vittorio, Parisi, Domenico·2004·Proceedings of the National Academy of Sciences
DOI 10.1073/pnas.0400054101PMC PMC365677
Open this paper in CoChat — free account

Abstract

The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic and protein networks), or technological problems (optimization of large infrastructures). Several types of algorithms exist for revealing the community structure in networks, but a general and quantitative definition of community is not implemented in the algorithms, leading to an intrinsic difficulty in the interpretation of the results without any additional nontopological information. In this article we deal with this problem by showing how quantitative definitions of community are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability. The algorithm is tested on artificial and real-world graphs. In particular, we show how the algorithm applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods. This type of local algorithm could open the way to applications to large-scale technological and biological systems.

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.1073/pnas.0400054101

Cites

31 of 31 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?

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: 16

  1. [2]Newman, M. E. J. (2003), SIAM Review 45 , 167-256.
  2. [8]Wagner, A. & Fell, D. A. (2001), Proc. R. Soc. London B 268 , 1803-1810.
  3. [11]Dunne, J. A., Williams, R. J. & Martinez, N. D. (2002), Proc. Natl. Acad. Sci. USA 99 , 12917-12922.
  4. [15]Newman, M. E. J. (2001), Proc. Natl. Acad. Sci. USA 98 , 404-409.
  5. [16]Rives, A. & Galitski, T. (2003), Proc. Natl. Acad. Sci. USA 100 , 1128-1133.
  6. [17]Flake, G. W., Lawrence, S. R., Giles, C. L. & Coetzee, F. M. (2002), IEEE Computer 35(3) , 66-71.
  7. [19]Girvan, M. & Newman, M. E .J. (2002), Proc. Natl. Acad. Sci. USA 99 , 7821-7826.
  8. [22]Newman, M. E .J. & Girvan, M. (2003), cond-mat/0308217. · arXiv
  9. [24]Wilkinson, D. & Huberman, B. A. (2002), cond-mat/0210147. · arXiv
  10. [25]Gleiser, P. & Danon, L. (2003), cond-mat/0307434. · arXiv
  11. [26]Guimer` a, R., Danon, L., D ´ iaz-Guilera, A., Giralt, F. & Arenas, A. (2002), cond-mat/0211498. · arXiv
  12. [27]Tyler, J. R., Wilkinson, D. M. & Huberman, B. A. (2003), cond-mat/0303264. · arXiv
  13. [28]Newman, M. E .J. (2003), cond-mat/0309508. · arXiv
  14. [31]Brandes U. (2001), Journal of Mathematical Sociology 25 , 163-177.
  15. [34]Bogu˜ na M., Pastor-Satorras R., D ´ iaz-Guilera A. & Arenas A. (2003), cond-mat/0309263. · arXiv
  16. [36]Caldarelli, G., Pastor-Satorras, R. & Vespignani A. (2002), cond-mat/0212026. · arXiv

Cited by

Sorted by citations

Related

Authors
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D.
Affiliations
University of Rome Tor Vergata (IT)
Corresponding author
Loreto, Vittorio
ORCID
Venue
Proceedings of the National Academy of Sciences
Publisher
National Academy of Sciences
Published
2004-02-23
Volume
101
Issue
9
Pages
2658-2663
ISSN
  • 0027-8424 (ISSN-L)
  • 1091-6490
DOI
10.1073/pnas.0400054101
PMC
PMC365677
OpenAlex
W2038920443
Cited by
2,450
References
31
Citations by year
2026: 36 · 2025: 69 · 2024: 69 · 2023: 97 · 2022: 126 · 2021: 116 · 2020: 133 · 2019: 120 · 2018: 161 · 2017: 141 · 2016: 130 · 2015: 136 · 2014: 186 · 2013: 147 · 2012: 139
FWCI
44.55
Type
journal article
Language
en
Open access
Locations
  • Proceedings of the National Academy of Sciences (publishedVersion)
  • Europe PMC (PubMed Central) (publishedVersion)
  • PubMed Central (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • IRIS Research product catalog (Sapienza University of Rome) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Bioinformatics and Genomic Networks
  • Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
Keywords
community structure, community detection, computational cost, research collaboration networks, large-scale networks, biological networks, technological networks
MeSH terms
Algorithms, Football, Humans, Metabolism, Models, Biological, Phylogeny, Proteins, Reproducibility of Results, Neural Networks, Computer

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