The DOI matches its Crossref record; 57 of the 59 references it cites were found in a registry or an index.
Finding and evaluating community structure in networks
Open accessAbstract
We propose and study a set of algorithms for discovering community structure in networks-natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.
Overview
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.
Integrity signals
Registry
Cites
Statistics
Verification
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.
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?
In the citing paper
“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 Newman & Girvan, 2004
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
(1979) · Cited by 43,841
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Statistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Self-citationAdhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502
Self-citationA set of measures of centrality based upon betweenness
Freeman, L. (1977) · Sociometry · doi:10.2307/3033543 · Cited by 10,557
Strogatz, S. H. (2001) · Nature · doi:10.1038/35065725 · Cited by 8,236
Network Flows: Theory, Algorithms, and Applications.
Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1994) · Journal of the Operational Research Society · doi:10.2307/2583863 · Cited by 8,121
Social Network Analysis: A Handbook.
Pappi, F. U., & Scott, J. P. (1993) · Contemporary Sociology A Journal of Reviews · doi:10.2307/2075047 · Cited by 5,964
Epidemic Spreading in Scale-Free Networks
Pastor‐Satorras, R., & Vespignani, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.3200 · Cited by 5,785
An Efficient Heuristic Procedure for Partitioning Graphs
Kernighan, B. W., & Lin, S. M. (1970) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1970.tb01770.x · Cited by 5,325
A faster algorithm for betweenness centrality*
Brandes, U. (2001) · Journal of Mathematical Sociology · doi:10.1080/0022250x.2001.9990249 · Cited by 5,075
The Large-Scale Organization of Metabolic Networks
Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35036627 · Cited by 4,972
An Information Flow Model for Conflict and Fission in Small Groups
Zachary, W. W. (1977) · Journal of Anthropological Research · doi:10.1086/jar.33.4.3629752 · Cited by 4,709
The structure of scientific collaboration networks
Newman, M. E. J. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.98.2.404 · Cited by 4,550
Self-citationOn power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/316188.316229 · Cited by 4,279
Diameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (1999) · Nature · doi:10.1038/43601 · Cited by 4,240
Bollobás, B. (1998) · Graduate texts in mathematics · doi:10.1007/978-1-4612-0619-4 · Cited by 3,867
Newman, M. (2002) · Physical review. E, Statistical, nonlinear, and soft matter physics · doi:10.1103/physreve.67.026126 · Cited by 3,130
Self-citationClasses of small-world networks
Amaral, L. A. N., Scala, A., Barthélémy, M., & Stanley, H. E. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.200327197 · Cited by 3,051
Friends and neighbors on the Web
Adamic, L. A., & Adar, E. (2003) · Social Networks · doi:10.1016/s0378-8733(03)00009-1 · Cited by 2,989
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00083-9 · Cited by 2,810
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/316194.316229 · Cited by 2,643
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Newman, M. E. J. (2001) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.64.016132 · Cited by 2,631
Self-citationLusseau, D., Schneider, K., Boisseau, O. J., Haase, P. A., Slooten, E., & Dawson, S. (2003) · Behavioral Ecology and Sociobiology · doi:10.1007/s00265-003-0651-y · Cited by 2,283
Introduction to algorithms [2nd ed.]
Cormen, T. H. (2001) · Cited by 1,902
O’Regan, G. (2023) · Texts in computer science · doi:10.1007/978-3-031-26212-8_4 · Cited by 1,614
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · doi:10.1093/acprof:oso/9780198515906.001.0001 · Cited by 1,563
Food-web structure and network theory: The role of connectance and size
Dunne, J. A., Williams, R. J., & Martinez, N. D. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.192407699 · Cited by 1,531
Self-similar community structure in a network of human interactions
Guimerà, R., Danon, L., Díaz-Guilera, A., Giralt, F., & Arenas, A. (2003) · Physical Review E · doi:10.1103/physreve.68.065103 · Cited by 1,515
How popular is your paper? An empirical study of the citation distribution
Redner, S. (1998) · The European Physical Journal B · doi:10.1007/s100510050359 · Cited by 1,509
Universal Behavior of Load Distribution in Scale-Free Networks
Goh, K.-I., Kahng, B., & Kim, D. (2001) · Physical Review Letters · doi:10.1103/physrevlett.87.278701 · Cited by 1,246
Collective dynamics of 'small-world' networks
Watts, D. J., & Strogatz, S. H. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356.301 · Cited by 1,087
GLEISER, P. M., & Danon, L. (2003) · Advances in Complex Systems · doi:10.1142/s0219525903001067 · Cited by 1,037
Self-organization and identification of Web communities
Flake, G. W., Lawrence, S., Giles, C. L., & Coetzee, F. M. (2002) · Computer · doi:10.1109/2.989932 · Cited by 1,019
The small world inside large metabolic networks
Wagner, A., & Fell, D. A. (2001) · Proceedings of the Royal Society B Biological Sciences · doi:10.1098/rspb.2001.1711 · Cited by 986
Epidemics and percolation in small-world networks
Moore, C., & Newman, M. E. J. (2000) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.61.5678 · Cited by 963
Self-citationStanford GraphBase: A Platform for Combinatorial Computing, The
Knuth, D. E. (1993) · Cited by 927
Computers and the Theory of Statistics: Thinking the Unthinkable
Efron, B. (1979) · SIAM Review · doi:10.1137/1021092 · Cited by 880
The emergent properties of a dolphin social network
Lusseau, D. (2003) · Proceedings of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rsbl.2003.0057 · Cited by 844
Breiger, R. L., Boorman, S. A., & Arabie, P. (1975) · Journal of Mathematical Psychology · doi:10.1016/0022-2496(75)90028-0 · Cited by 828
Infection dynamics on scale-free networks
May, R. M., & Lloyd, A. L. (2001) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.64.066112 · Cited by 762
Email as Spectroscopy: Automated Discovery of Community Structure within Organizations
Tyler, J. R., Wilkinson, D. M., & Huberman, B. A. (2003) · Communities and Technologies · doi:10.1007/978-94-017-0115-0_5 · Cited by 433
Subnetwork hierarchies of biochemical pathways
Holme, P., Huss, M., & Jeong, H. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg033 · Cited by 369
Marchiori, M., & Latora, V. (2000) · Physica A Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(00)00311-3 · Cited by 343
Evolution of Networks: From Biological Nets to the Internet and WWWPreprint
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · RePEc: Research Papers in Economics · Cited by 315
Robust Patterns in Food Web Structure
Camacho, J., Guimerà, R., & Amaral, L. A. N. (2002) · Physical Review Letters · doi:10.1103/physrevlett.88.228102 · Cited by 296
On power-law relationships of the internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356.195 · Cited by 269
Epidemic Spreading in Scale-Free Networks
Pastor‐Satorras, R., & Vespignanj, A. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356.493 · Cited by 247
Anthonisse, J. M. (1971) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · Cited by 244
Diameter of the world-wide web
Albert, R., Jeong, H. S., & Barabasi, A.-L. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356.182 · Cited by 225
Origin of degree correlations in the Internet and other networks
Park, J. M., & Newman, M. E. J. (2003) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.68.026112 · Cited by 222
Self-citationMean-field-type equations for spread of epidemics: the ‘small world’ model
Kleczkowski, A., & Grenfell, B. T. (1999) · Physica A Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(99)00393-3 · Cited by 87
Email as Spectroscopy: Automated Discovery of Community Structure within OrganizationsPreprint
Tyler, J. R., Wilkinson, D. M., & Huberman, B. A. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.cond-mat/0303264 · Cited by 45
Grousson, M., Tarjus, G., & Viot, P. (2002) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.65.065103 · Cited by 22
Finding Communities of Related GenesPreprint
Wilkinson, D. M., & Huberman, B. A. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.cond-mat/0210147 · Cited by 9
Flagged first, then by citations
2 of the 59 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424
Modularity and community structure in networks
Newman, M. E. J. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0601602103 · Cited by 12,256
Self-citationFortunato, 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
Data clustering: 50 years beyond K-means
Jain, A. K. (2009) · Pattern Recognition Letters · doi:10.1016/j.patrec.2009.09.011 · Cited by 10,021
Metadata
- Authors
- Newman, M. E. J., & Girvan, M.
- Affiliations
- Santa Fe Institute (US)
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2004-02-26
- Volume
- 69
- Issue
- 2
- Pages
- 026113-026113
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W2095293504
- Cited by
- 13,931
- References
- 59
- Citations by year
- 2026: 370 · 2025: 648 · 2024: 663 · 2023: 685 · 2022: 816 · 2021: 872 · 2020: 880 · 2019: 963 · 2018: 988 · 2017: 803 · 2016: 888 · 2015: 781 · 2014: 844 · 2013: 787 · 2012: 655
- FWCI
- 105.23
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review E (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- 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 structure, network clustering, edge deletion, betweenness centrality, number of communities, network partitioning, complex networks
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
