Community structure in social and biological networks
Open accessThe DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Abstract
A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known—a collaboration network and a food web—and find that it detects significant and informative community divisions in both cases.
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.
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?
The cited source doesn’t support the claim as written.
In the citing paper
“Community detection algorithms such as Louvain (Blondel et al., 2008) or Newman Girvan (Girvan and Newman, 2002) determine the approximate number of communities by optimizing modularity, or the density of links within communities versus links between communities.”
From Mapping the multiscale structure of biological systems (2021) · cites this paper as Girvan and Newman, 2002
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measuredThe check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“Although prosocial behaviors in different strategic domains may manifest in different ways, such as trust games or dictator games, the desire to pay costs to benefit others has a substantial degree of domain generality [49].”
From Strategy evolution on dynamic networks (2023) · cites this paper as [49]
Experimental — accuracy not yet measured
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
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
A Set of Measures of Centrality Based on Betweenness
Freeman, L. C. (1977) · Sociometry · doi:10.2307/3033543 · Cited by 10,295 · cited 4×
“To find which edges in a network are most between other pairs of vertices, we generalize Freeman’s betweenness centrality to edges and define the edge betweenness of an edge as the number of shortest paths between pairs of vertices that run along it.”
BackgroundInfluentialStrogatz, S. H. (2001) · Nature · doi:10.1038/35065725 · Cited by 8,302 · cited 2×
“The degree of a vertex in a network is the number of other vertices to which it is connected, and one finds that there are typically many vertices in a network with low degree and a small number with high degree, the precise distribution often following a power-law or exponential form [1, 5, 15].”
BackgroundNetwork Flows: Theory, Algorithms, and Applications.
Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1994) · The Journal of the Operational Research Society · doi:10.2307/2583863 · Cited by 8,034 · cited 1×
“Numbers of independent paths can be computed quickly by using polynomial-time ‘‘max-flow’’ algorithms such as the augmenting path algorithm (22).”
Method(2017) · The SAGE Encyclopedia of Communication Research Methods · doi:10.4135/9781483381411.n575 · Cited by 6,008
Social Network Analysis: A Handbook.
Pappi, F. U., & Scott, J. (1993) · Contemporary Sociology · doi:10.2307/2075047 · Cited by 5,969
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
The small-world problem: (400002009-005)
Milgram, S. (1967) · PsycEXTRA Dataset · doi:10.1037/e400002009-005 · Cited by 4,790
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,704
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,482 · cited 2×
“Detecting communities in, for instance, the large collaboration networks [6] or subsets of the Web graph [9] that have been studied recently, would be entirely unfeasible.”
BackgroundSelf-citationDiameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-L. (1999) · Nature · doi:10.1038/43601 · Cited by 4,260
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/316188.316229 · Cited by 4,196 · cited 2×
“Examples include social networks [2, 3, 4] such as acquaintance networks [5] and collaboration networks [6], technological networks such as the Internet [7], the World-Wide Web [8, 9], and power grids [4, 5], and biological networks such as neural networks [4], food webs [10], and metabolic networks [11, 12].”
BackgroundA New Status Index Derived from Sociometric Analysis
Katz, L. (1953) · Psychometrika · doi:10.1007/bf02289026 · Cited by 3,866
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2001) · Physical Review E · doi:10.1103/physreve.64.026118 · Cited by 3,648 · cited 1×
“This effect is quantified by the clustering coefficient C [4, 18], defined by”
MethodSelf-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
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 · cited 3×
“Detecting communities in, for instance, the large collaboration networks [6] or subsets of the Web graph [9] that have been studied recently, would be entirely unfeasible.”
BackgroundScientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.016132 · Cited by 2,613
Self-citationOn 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,613
Scientific collaboration networks. I. Network construction and fundamental results
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.016131 · Cited by 2,076
Self-citationHow 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 · cited 1×
“Communities in a social network might represent real social groupings, perhaps by interest or background; communities in a citation network [19] might represent related papers on a single topic; communities in a metabolic network might represent cycles and other functional groupings; communities in the Web might repre…”
BackgroundSimple rules yield complex food webs
Williams, R. J., & Martinez, N. D. (2000) · Nature · doi:10.1038/35004572 · Cited by 1,487
Structure of Growing Networks with Preferential Linking
Dorogovtsev, S. N., Mendes, J. F. F., & Samukhin, A. N. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.4633 · Cited by 1,307
Menger, K. (1927) · Fundamenta Mathematicae · doi:10.4064/fm-10-1-96-115 · Cited by 1,216
Connectivity of Growing Random Networks
Krapivsky, P. L., Redner, S., & Leyvraz, F. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.4629 · Cited by 1,197
The Seasonal Dynamics of The Chesapeake Bay Ecosystem
Baird, D., & Ulanowicz, R. E. (1989) · Ecological Monographs · doi:10.2307/1943071 · Cited by 824 · cited 3×
“This network was originally compiled by Baird and Ulanowicz (27) and contains 33 vertices representing the ecosystem’s most prominent taxa.”
MethodInfluentialConstant Connectance in Community Food Webs
Martinez, N. D. (1992) · The American Naturalist · doi:10.1086/285382 · Cited by 470 · cited 1×
“, the number of edges scales as the square of the number of vertices rather than scaling linearly [27].”
BackgroundFell, D. A., & Wagner, A. (2000) · Nature Biotechnology · doi:10.1038/81025 · Cited by 419 · cited 1×
“Examples include social networks [2, 3, 4] such as acquaintance networks [5] and collaboration networks [6], technological networks such as the Internet [7], the World-Wide Web [8, 9], and power grids [4, 5], and biological networks such as neural networks [4], food webs [10], and metabolic networks [11, 12].”
BackgroundThe Cohesiveness of Blocks In Social Networks: Node Connectivity and Conditional Density
White, D. R., & Harary, F. (2001) · Sociological Methodology · doi:10.1111/0081-1750.00098 · Cited by 296 · cited 1×
“To this end, we have selected two datasets representing real-world networks for which the community structure is already known from other sources.”
BackgroundIn search of operational trophospecies in a tropical aquatic food web
Yodzis, P., & Winemiller, K. (1999) · Oikos · doi:10.2307/3546748 · Cited by 132
Freeman, L. C., Mitchell, J. C., & Ziegler, R. (1978) · Social Networks · doi:10.1016/0378-8733(78)90010-2 · Cited by 54
Research works printed but not linked: 1
- S Milgram Psychol Today 2, 60–67 (1967).
Cited by
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
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
“Recently a number of authors have had success with methods based on “edge betweenness,” which is the count of how many geodesic paths between vertices run along each edge in the network [171, 185, 197, 422].”
Self-citationFinding 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
“Since the publication of our first paper on this topic [25], several other authors have made use of the shortest-path version of our algorithm.”
BackgroundSelf-citationModularity 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
“(We note in passing that in principle the fine-tuning method could also be used to refine results from other modularity maximization algorithms, such as the extremal optimization algorithm of ref.”
BackgroundMethodSelf-citationComplex brain networks: graph theoretical analysis of structural and functional systems
Bullmore, E., & Sporns, O. (2009) · Nature Reviews Neuroscience · doi:10.1038/nrn2575 · Cited by 11,820
“There are various algorithms that estimate the modularity of a network, many of them based on hierarchical clustering 23 .”
Background
Metadata
- Authors
- Girvan, M., & Newman, M. E. J.
- Affiliations
- Santa Fe Institute (US)
- Venue
- Proceedings of the National Academy of Sciences
- Publisher
- National Academy of Sciences
- Published
- 2002-06-11
- Volume
- 99
- Issue
- 12
- Pages
- 7821-7826
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- PMC
- PMC122977
- OpenAlex
- W1971421925
- Cited by
- 15,502
- References
- 32
- Citations by year
- 2026: 377 · 2025: 665 · 2024: 733 · 2023: 805 · 2022: 889 · 2021: 990 · 2020: 1050 · 2019: 1053 · 2018: 1042 · 2017: 959 · 2016: 924 · 2015: 862 · 2014: 905 · 2013: 828 · 2012: 714
- FWCI
- 50.71
- Type
- journal article
- Language
- en
- Open access
- green
- www.ncbi.nlm.nih.gov
- Locations
- Proceedings of the National Academy of Sciences (publishedVersion)
- Europe PMC (PubMed Central) (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (9870631, 0109086, 9910217)
- 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 › Mathematics › Discrete Mathematics and Combinatorics › Graph theory and applications
- Keywords
- community structure, community detection, social networks, biological networks, centrality indices, network topology, collaboration networks, food webs, small-world property, power-law degree distribution, network transitivity
- MeSH terms
- Algorithms, Animals, Computer Simulation, Humans, Models, Theoretical, Nerve Net, Social Behavior, Neural Networks, Computer, Community 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
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.