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
Research works printed but not linked: 1
- S Milgram Psychol Today 2, 60–67 (1967).
Cited by
Items 1,001–1,049 of 1,049
Spatial Guilds in the Serengeti Food Web Revealed by a Bayesian Group Model
Baskerville, E. B., Dobson, A. P., Bedford, T., Allesina, S., Anderson, T. M., & Pascual, M. (2011) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002321 · Cited by 113
“In this definition, compartments are alternately referred to as modules, clusters, or ‘‘communities’’ [5], and are defined by high link density within groups and low link density between them.”
BackgroundBETZEL, R. F., GRIFFA, A., AVENA-KOENIGSBERGER, A., GOÑI, J., THIRAN, J.-P., HAGMANN, P., & SPORNS, O. (2013) · Network Science · doi:10.1017/nws.2013.19 · Cited by 113
“Many complex networks exhibit community structure, defined for example by clustered edge distributions such that vertices (nodes) in the same community preferentially link to one another (Guimera & Amaral, 2005; Girvan & Newman, 2002; Newman & Girvan, 2004).”
BackgroundChen, C., Sun, F., Zhang, M., & Ding, B. (2022) · Proceedings of the ACM Web Conference 2022 · doi:10.1145/3485447.3511997 · Cited by 110
“One solution is to leverage community detection methods [14, 22] to partition the training data, so that the collaborative information of the data can be preserved to a great extent.”
BackgroundMethodChanges in cognitive state alter human functional brain networks
Moussa, M. N., Vechlekar, C. D., Burdette, J. H., Steen, M. R., Hugenschmidt, C. E., & Laurienti, P. J. (2011) · Frontiers in Human Neuroscience · doi:10.3389/fnhum.2011.00083 · Cited by 99
“A network’s community structure is defined by the cliques or groups of clustered nodes that are more highly interconnected with each other than with other nodes in the network (Girvan and Newman, 2002).”
BackgroundSocial networking in the Columbian ground squirrel, Spermophilus columbianus
Manno, T. G. (2008) · Animal Behaviour · doi:10.1016/j.anbehav.2007.09.025 · Cited by 96
Inferring social structure from temporal data
Psorakis, I., Voelkl, B., Garroway, C. J., Radersma, R., Aplin, L. M., Crates, R. A., Culina, A., Farine, D. R., Firth, J. A., Hinde, C. A., et al. (2015) · Behavioral Ecology and Sociobiology · doi:10.1007/s00265-015-1906-0 · Cited by 95
“For producing the data stream, we first generated a reference (ground-truth) network of a hypothetical social network of 128 birds and 4 flocks, using the Girvan– Newman random graph model (Girvan and Newman 2002).”
Social goods dilemmas in heterogeneous societies
McAvoy, A., Allen, B., & Nowak, M. A. (2020) · Nature Human Behaviour · doi:10.1038/s41562-020-0881-2 · Cited by 94
“To illustrate the effects of the division of real-world interaction topologies on evolutionary dynamics, we consider Zachary’s karate club (Zachary, 1977), a, and the subsequent split of the karate club into two disjoint groups (Girvan and Newman, 2002), b and c.”
MethodInvestigating Italian disinformation spreading on Twitter in the context of 2019 European elections
Pierri, F., Artoni, A., & Ceri, S. (2020) · PLOS ONE · doi:10.1371/journal.pone.0227821 · Cited by 93
Strategy evolution on dynamic networks
Su, Q., McAvoy, A., & Plotkin, J. B. (2023) · Nature Computational Science · doi:10.1038/s43588-023-00509-z · Cited by 97
“Groups and communities are more likely to form among people with close geographical locations and similar religion, culture and affiliations 49,50 , but connection densities will be altered over time.”
BackgroundLima da Cruz, R. V., Moulin, T. C., Petiz, L. L., & Leão, R. N. (2018) · Frontiers in Molecular Neuroscience · doi:10.3389/fnmol.2018.00312 · Cited by 84
Structure and evolution of co-authorship network in an interdisciplinary research field
Liu, P., & Xia, H. (2015) · Scientometrics · doi:10.1007/s11192-014-1525-y · Cited by 84
“High value of modularity means that the network has a clear community structure; and the network is comprised of multiple modules or communities with dense intra-communal links but less-dense inter-communal links (Girvan and Newman 2002).”
BackgroundDetecting multiple communities using quantum annealing on the D-Wave system
Negre, C. F. A., Ushijima-Mwesigwa, H., & Mniszewski, S. M. (2020) · PLOS ONE · doi:10.1371/journal.pone.0227538 · Cited by 80
A survey on literature based discovery approaches in biomedical domain
Gopalakrishnan, V., Jha, K., Jin, W., & Zhang, A. (2019) · Journal of Biomedical Informatics · doi:10.1016/j.jbi.2019.103141 · Cited by 76
Lanke, V., Moolamalla, S. T. R., Roy, D., & Vinod, P. K. (2018) · Frontiers in Aging Neuroscience · doi:10.3389/fnagi.2018.00153 · Cited by 76
“The edge betweenness centrality measure was computed using igraph R package (Girvan and Newman, 2002).”
MethodMapping the multiscale structure of biological systems
Schaffer, L. V., & Ideker, T. (2021) · Cell Systems · doi:10.1016/j.cels.2021.05.012 · Cited by 75
“Community detection algorithms such as Louvain (Blondel et al., 2008) or Newman Girvan (Girvan and Newman, 2002) determinethe approximatenumber ofcommunitiesbyopti-mizing modularity, or the density of links within communities versus links between communities.”
MethodRich-club in the brain’s macrostructure: Insights from graph theoretical analysis
Kim, D.-J., & Min, B.-K. (2020) · Computational and Structural Biotechnology Journal · doi:10.1016/j.csbj.2020.06.039 · Cited by 73
“Network modules (i.e., communities or clusters) are defined by a set of network elements with a number of interconnections within each module and fewer connections among modules [11,12].”
BackgroundEcological subsystems via graph theory: the role of strongly connected components
Allesina, S., Bodini, A., & Bondavalli, C. (2005) · Oikos · doi:10.1111/j.0030-1299.2005.13082.x · Cited by 71
“For the Chesapeake Bay the same result was obtained by Girvan and Newman (2002), who used new approach to clustering based on the concept of ‘‘edge betweeness’’ applied to the network graph and by Krause et al.”
BackgroundMethodRichmond, S., Johnson, K. A., Seal, M. L., Allen, N. B., & Whittle, S. (2016) · Neuroscience & Biobehavioral Reviews · doi:10.1016/j.neubiorev.2016.08.024 · Cited by 70
A Complex Network Approach to Urban Growth
Andersson, C., Frenken, K., & Hellervik, A. (2006) · Environment and Planning A: Economy and Space · doi:10.1068/a37418 · Cited by 67
Conceptual and practical advances in fish stock delineation
Pita, A., Casey, J., Hawkins, S. J., Villarreal, M. R., Gutiérrez, M.-J., Cabral, H., Carocci, F., Abaunza, P., Pascual, S., & Presa, P. (2016) · Fisheries Research · doi:10.1016/j.fishres.2015.10.029 · Cited by 66
Williamson, C. M., Franks, B., & Curley, J. P. (2016) · Frontiers in Behavioral Neuroscience · doi:10.3389/fnbeh.2016.00152 · Cited by 64
“This approach has been well developed and validated for identifying community structure in species as diverse as whales, dolphins, birds and primates (Girvan and Newman, 2002; Lusseau and Newman, 2004; Lusseau et al., 2008; Griffin and Nunn, 2011; Aplin et al., 2013).”
BackgroundMethodFederated Region-Learning: An Edge Computing Based Framework for Urban Environment Sensing
Hu, B., Gao, Y., Liu, L., & Ma, H. (2018) · 2018 IEEE Global Communications Conference (GLOBECOM) · doi:10.1109/glocom.2018.8647649 · Cited by 67
Digital game-based language learning for vocabulary development
Chowdhury, M., Dixon, L., Kuo, L.-J., Donaldson, J. P., Eslami, Z., Viruru, R., & Luo, W. (2024) · Computers and Education Open · doi:10.1016/j.caeo.2024.100160 · Cited by 64
Markovič, R., Stožer, A., Gosak, M., Dolenšek, J., Marhl, M., & Rupnik, M. S. (2015) · Scientific Reports · doi:10.1038/srep07845 · Cited by 61
Automatic discovery of cell types and microcircuitry from neural connectomics
Jonas, E., & Kording, K. (2015) · eLife · doi:10.7554/elife.04250 · Cited by 51
“Commonly used algorithms include community-based-detection methods 9 , and stochastic block models 10 .”
MethodMultilevel Combinatorial Optimization across Quantum Architectures
Ushijima-Mwesigwa, H., Shaydulin, R., Negre, C. F. A., Mniszewski, S. M., Alexeev, Y., & Safro, I. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3425607 · Cited by 57
“tructure (portfolio optimization problem and road network), this preserves their structural properties. GirvanNewmanis a synthetic graph generated using the model introduced by Girvan and Newman (GN) [31]. The graph lancichinetti1 is a synthetic graph generated using a generalization of the GN model that allows for he…”
MethodGroup-in-a-Box Layout for Multi-faceted Analysis of Communities
Rodrigues, E. M., Milic-Frayling, N., Smith, M., Shneiderman, B., & Hansen, D. (2011) · 2011 IEEE Third Int'l Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third Int'l Conference on Social Computing · doi:10.1109/passat/socialcom.2011.139 · Cited by 57
“The Girvan–Newman algorithm [7] takes a divisive hierarchical approach.”
MethodA data-driven approach to post-stroke aphasia classification and lesion-based prediction
Landrigan, J.-F., Zhang, F., & Mirman, D. (2021) · Brain · doi:10.1093/brain/awab010 · Cited by 54
“The particular CDA algorithm was the edge-betweenness community detection algorithm, 37,38 implemented through functions provided by the iGraph package available for R (Version 1.1.2 39 ).”
MethodInfluentialCanright, G., & Engø-Monsen, K. (2004) · Science of Computer Programming · doi:10.1016/j.scico.2003.12.008 · Cited by 51
“Our approach is dual to that of Girvan and Newman [5], in the sense that their approach defines regions by finding their boundaries, while ours finds first their centres.”
BackgroundResultGenerative models of rich clubs in Hebbian neuronal networks and large-scale human brain networks
Vértes, P. E., Alexander-Bloch, A., & Bullmore, E. T. (2014) · Philosophical Transactions of the Royal Society B: Biological Sciences · doi:10.1098/rstb.2013.0531 · Cited by 50
Cluster-based statistics for brain connectivity in correlation with behavioral measures.
Han, C. E., Yoo, S. W., Seo, S. W., Na, D. L., & Seong, J.-K. (2013) · PLoS ONE · doi:10.1371/journal.pone.0072332 · Cited by 49
“Graph theoretical approaches revealed novel characteristics of brain organization, including small-world topology [1–4], scale-free characteristics [4–6], global integration [1,7–9], modular structure [4,10,11], and hierarchical organization [12–14] of the brain networks.”
BackgroundSynteny-Guided Resolution of Gene Trees Clarifies the Functional Impact of Whole-Genome Duplications
Parey, E., Louis, A., Cabau, C., Guiguen, Y., Roest Crollius, H., & Berthelot, C. (2020) · Molecular Biology and Evolution · doi:10.1093/molbev/msaa149 · Cited by 49
Dynamic allostery-based molecular workings of kinase:peptide complexes
Ahuja, L. G., Aoto, P. C., Kornev, A. P., Veglia, G., & Taylor, S. S. (2019) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1900163116 · Cited by 49
“Community networks for the 7 complexes were determined using the Girvan – Newman approach (40) on the mutual information matrices (Figs.”
MethodBridge ties bind collective memories
Momennejad, I., Duker, A., & Coman, A. (2019) · Nature Communications · doi:10.1038/s41467-019-09452-y · Cited by 45
Community Detection in Quantum Complex Networks
Faccin, M., Migdał, P., Johnson, T. H., Bergholm, V., & Biamonte, J. D. (2014) · Physical Review X · doi:10.1103/physrevx.4.041012 · Cited by 43
“In this paper, we extend the concept of community detection from classical to quantum systems — a crucial missing component of a theory of complex networks based on quantum mechanics.”
BackgroundEscaping the Survival Trap: Network Transition among Early-Career Freelance Songwriters
Lee, Y. G., & Gargiulo, M. (2022) · Administrative Science Quarterly · doi:10.1177/00018392211055198 · Cited by 41
“We applied a communitydetection algorithm (Girvan and Newman, 2002) to the main component of the collaboration network to identify cohesive subgroups and examined the modularity associated with the optimal partition as well as the stylistic similarity of the songs that songwriters created within and between these part…”
MethodCorrelation between structure and temperature in prokaryotic metabolic networks
Takemoto, K., Nacher, J. C., & Akutsu, T. (2007) · BMC Bioinformatics · doi:10.1186/1471-2105-8-303 · Cited by 40
“And note that the clusteringcoefficient-based modularity is different from the edgebetweenness-based modularity [21] and the flux-balanceanalysis-based modularity [22].”
BackgroundSamara, Z., Evers, E. A. T., Peeters, F., Uylings, H. B. M., Rajkowska, G., Ramaekers, J. G., & Stiers, P. (2018) · Biological Psychiatry: Cognitive Neuroscience and Neuroimaging · doi:10.1016/j.bpsc.2018.01.004 · Cited by 40
Activation of Functional Brain Networks in Children With Psychogenic Non-epileptic Seizures
Radmanesh, M., Jalili, M., & Kozlowska, K. (2020) · Frontiers in Human Neuroscience · doi:10.3389/fnhum.2020.00339 · Cited by 35
The multiple, interacting levels of cognitive systems (MILCS) perspective on group cognition
Goldstone, R. L., & Theiner, G. (2017) · Philosophical Psychology · doi:10.1080/09515089.2017.1295635 · Cited by 31
“…(i.e., brains) and collective social networks (Barabasi & Albert, 1999; Boccaletti, Latora, Moreno, Chavez, & Hwang, 2006; Bullmore & Sporns, 2009; Girvan & Newman, 2002), often with the felicitous outcome of developing insight into both kinds of networks through their conceptual unification.”
BackgroundDorning, J., & Harris, S. (2019) · Scientific Reports · doi:10.1038/s41598-019-56713-3 · Cited by 28
Wang, T., Peng, Q., Liu, B., Liu, Y., & Wang, Y. (2020) · Frontiers in Bioengineering and Biotechnology · doi:10.3389/fbioe.2020.00418 · Cited by 27
“…Zachary’s karate club network (Zachary, 1977), UKfaculty social network (Nepusz et al., 2008), Dolphin Social Network (Lusseau et al., 2003), College football game network (Girvan and Newman, 2002), US Political Books network (Krebs, 2004), and Cora citation network (Fakhraei et al., 2015).”
BackgroundHiVG: A hierarchical indoor visibility-based graph for navigation guidance in multi-storey buildings
Zhou, Z., Weibel, R., Richter, K.-F., & Huang, H. (2022) · Computers, Environment and Urban Systems · doi:10.1016/j.compenvurbsys.2021.101751 · Cited by 24
“Inspired by the classical Girvan-Newman algorithm for community detection in complex networks by means of top-down graph partitioning (Girvan & Newman, 2002; Newman & Girvan, 2004), we propose an edge-function-based graph partitioning algorithm to build our hierarchy.”
MethodMiyoshi, T., Tanioka, K., Yamamoto, S., Yadohisa, H., Hiroyasu, T., & Hiwa, S. (2020) · Frontiers in Human Neuroscience · doi:10.3389/fnhum.2019.00473 · Cited by 16
“Therefore, we used the number of communities detected by Newman clustering (Girvan and Newman, 2002) on the thresholded network as a cost criterion.”
MethodStructural host-virus interactome profiling of intact infected cells
(2025) · doi:10.1038/s41467-025-61618-z · Cited by 15
“The resulting network was clustered with the edge-betweenness algorithm 47 using in-house R scripts and the edge.”
Castillo-de-Mesa, J., Méndez-Domínguez, P., Carbonero-Muñoz, D., & Gómez-Jacinto, L. (2021) · Redes. Revista hispana para el análisis de redes sociales · doi:10.5565/rev/redes.913 · Cited by 32
Szabó, G., Norocel, O. C., & Bene, M. (2019) · Problems of Post-Communism · doi:10.1080/10758216.2018.1460208 · Cited by 13
Lalit, F., & Jose, A. M. (2025) · Nucleic Acids Research · doi:10.1093/nar/gkae1246 · Cited by 3
Tantlevskij, I. R., Evmenova, E., & Gromov, D. (2024) · Humanities and Social Sciences Communications · doi:10.1057/s41599-024-02911-y · Cited by 1
“This problem is well known as community detection, see, e.g., Girvan and Newman (2002); Newman (2004); Porter et al. (2009).”
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.