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
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 .”
BackgroundComplex network measures of brain connectivity: Uses and interpretations
Rubinov, M., & Sporns, O. (2010) · NeuroImage · doi:10.1016/j.neuroimage.2009.10.003 · Cited by 11,522
“This composition, known as the network's modular structure (community structure), is revealed by subdividing the network into groups of nodes, with a maximally possible number of withingroup links, and a minimally possible number of between-group links (Girvan and Newman, 2002).”
BackgroundFortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
“The algorithm finds very good estimates of the modularity maximum, and performs very well on the benchmark of Girvan and Newman (Girvan and Newman, 2002) (Section XV.”
BackgroundMethodInfluentialNetwork biology: understanding the cell's functional organization
Barabási, A.-L., & Oltvai, Z. N. (2004) · Nature Reviews Genetics · doi:10.1038/nrg1272 · Cited by 7,903
Finding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
“As an example of the application of this algorithm we use it to analyze a network of items for sale on the web-site of a large online retailer, items in the network being linked if they are frequently purchased by the same buyer.”
MethodSelf-citationChen, C. (2006) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.20317 · Cited by 6,433
“This feature has been used in community-finding algorithms to identify and separate clusters (Girvan & Newman, 2002).”
MethodFast algorithm for detecting community structure in networks
Newman, M. E. J. (2004) · Physical Review E · doi:10.1103/physreve.69.066133 · Cited by 5,406
“601 for the best split reported in [5].”
BackgroundMethodInfluentialSelf-citationUncovering the overlapping community structure of complex networks in nature and society
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005) · Nature · doi:10.1038/nature03607 · Cited by 5,373
“[16]: it tends to stay together mostly with the words of the community related to “light”, while most of its other communities ( e.g. , those related to “colors”, see Fig.”
BackgroundNetwork medicine: a network-based approach to human disease
Barabási, A.-L., Gulbahce, N., & Loscalzo, J. (2011) · Nature Reviews Genetics · doi:10.1038/nrg2918 · Cited by 5,034
Finding community structure in networks using the eigenvectors of matrices
Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.74.036104 · Cited by 4,761
“Social networks [5], biochemical networks [7, 8, 9], and information networks such as the web [10], have all been shown to possess strong community structure, a finding that has substantial practical implications for our understanding of the systems these networks represent.”
BackgroundSelf-citationAn 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
Maps of random walks on complex networks reveal community structure
Rosvall, M., & Bergstrom, C. T. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0706851105 · Cited by 4,583
Hierarchical Organization of Modularity in Metabolic Networks
Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barabási, A.-L. (2002) · Science · doi:10.1126/science.1073374 · Cited by 4,224
“4a, bottom, and Ref.”
InfluentialStatistical physics of social dynamics
Castellano, C., Fortunato, S., & Loreto, V. (2009) · Reviews of Modern Physics · doi:10.1103/revmodphys.81.591 · Cited by 4,119
Functional cartography of complex metabolic networks
Guimerà, R., & Nunes Amaral, L. A. (2005) · Nature · doi:10.1038/nature03288 · Cited by 3,983
“We compare our algorithm to the Girvan-Newman algorithm 5,18 , which is the reference algorithm for module identification 11,18,19 .”
BackgroundMethodInfluentialSynchronization in complex networks
Arenas, A., Díaz-Guilera, A., Kurths, J., Moreno, Y., & Zhou, C. (2008) · Physics Reports · doi:10.1016/j.physrep.2008.09.002 · Cited by 3,713
“This property promises to be specially adequate to unveil structure-function relationships in complex networks [21, 22, 23, 24].”
BackgroundMethodInfluentialNear linear time algorithm to detect community structures in large-scale networks
Raghavan, U. N., Albert, R., & Kumara, S. (2007) · Physical Review E · doi:10.1103/physreve.76.036106 · Cited by 3,502
Spread of epidemic disease on networks
Newman, M. E. J. (2002) · Physical Review E · doi:10.1103/physreve.66.016128 · Cited by 3,218
Self-citationMolecular ecological network analyses
Deng, Y., Jiang, Y.-H., Yang, Y., He, Z., Luo, F., & Zhou, J. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-113 · Cited by 3,196
“Several studies demonstrated that metabolic networks are usually accompanied by a hierarchical modularity [37,44].”
BackgroundNewman, M. E. J. (2003) · Physical Review E · doi:10.1103/physreve.67.026126 · Cited by 3,087
“(2), consider the network studied by Girvan and Newman [16] representing the timetable of American college football games, in which vertices represent universities and colleges, and edges represent regular season games between teams during the year in question.”
BackgroundSelf-citationMeasurement and analysis of online social networks
Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P., & Bhattacharjee, B. (2007) · Proceedings of the 7th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1298306.1298311 · Cited by 3,057
Benchmark graphs for testing community detection algorithms
Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008) · Physical Review E · doi:10.1103/physreve.78.046110 · Cited by 3,051
Resolution limit in community detection
Fortunato, S., & Barthélemy, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0605965104 · Cited by 3,024
Comparing community structure identification
Danon, L., Díaz-Guilera, A., Duch, J., & Arenas, A. (2005) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2005/09/p09008 · Cited by 2,872
“r communities containing 32 nodes each. A pair of nodes both of which belong to the same community are linked with probability p in, and a pair which belong to 19 Reference Alias Order [25] NG O(m2n) [11] GN O(n2m) [29] FLM O(n4) [23] RCCLP O(n2) [35] NF O(nlog2n) [43], DMSA O(n3) [43], DMCA O(n3) [13] EM O(mhk2i) [14…”
BackgroundMethodInfluentialBuckner, R. L., Sepulcre, J., Talukdar, T., Krienen, F. M., Liu, H., Hedden, T., Andrews-Hanna, J. R., Sperling, R. A., & Johnson, K. A. (2009) · The Journal of Neuroscience · doi:10.1523/jneurosci.5062-08.2009 · Cited by 2,862
“In terms of network analysis, these distinct groupings may reflect separate “communities” (Girvan and Newman, 2002) or “modules” (Guimerà et al.”
BackgroundLink prediction in complex networks: A survey
Lü, L., & Zhou, T. (2011) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.11.027 · Cited by 2,819
“The stochastic blockmodel can capture the community structure [22], role-to-role connections [94,95] and maybe other factors for the establishing of connections, especially when the group membership plays a considerable role in determining how nodes interact with each other, which usually could not be well described b…”
BackgroundWhy we twitter: understanding microblogging usage and communities
Java, A., Song, X., Finin, T., & Tseng, B. (2007) · Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis · doi:10.1145/1348549.1348556 · Cited by 2,645
“In social network area, Newman and Girvan [13, 7] proposed a metric called modularity to measure the strength of the community structure.”
BackgroundThe modularity of pollination networks
Olesen, J. M., Bascompte, J., Dupont, Y. L., & Jordano, P. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0706375104 · Cited by 2,639
Newman, M. E. J. (2004) · Physical Review E · doi:10.1103/physreve.70.056131 · Cited by 2,476
“[27].”
BackgroundMethodInfluentialSelf-citationCharacterization of complex networks: A survey of measurements
Costa, L. D. F., Rodrigues, F. A., Travieso, G., & Villas Boas, P. R. (2007) · Advances in Physics · doi:10.1080/00018730601170527 · Cited by 2,475
“tigation of small-world networks [8], Barabási and Albert’s characterization of scale-free models [9], and Girvan and Newman’s identification of the community structures present in many networks (e.g. [10]). Although graph theory is a well-established and developed area in mathematics and theoretical computer science (…”
BackgroundMethodInfluentialA measure of betweenness centrality based on random walks
Newman, M. E. J. (2005) · Social Networks · doi:10.1016/j.socnet.2004.11.009 · Cited by 2,461
Self-citationDefining and identifying communities in networks
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0400054101 · Cited by 2,450
Data-Driven Phenotypic Dissection of AML Reveals Progenitor-like Cells that Correlate with Prognosis
Levine, J. H., Simonds, E. F., Bendall, S. C., Davis, K. L., Amir, E.-A. D., Tadmor, M. D., Litvin, O., Fienberg, H. G., Jager, A., Zunder, E. R., et al. (2015) · Cell · doi:10.1016/j.cell.2015.05.047 · Cited by 2,303
“To this end we borrow from the social network field, which has developed powerful algorithms to partition large social networks into communities (Girvan and Newman, 2002).”
Newman, M. (2018) · doi:10.1093/oso/9780198805090.001.0001 · Cited by 2,297
Self-citationRajaraman, A., & Ullman, J. D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139058452 · Cited by 2,262
Community detection algorithms: A comparative analysis
Lancichinetti, A., & Fortunato, S. (2009) · Physical Review E · doi:10.1103/physreve.80.056117 · Cited by 2,177
Hierarchical structure and the prediction of missing links in networks
Clauset, A., Moore, C., & Newman, M. E. J. (2008) · Nature · doi:10.1038/nature06830 · Cited by 2,171
Self-citationCommunity Structure in Time-Dependent, Multiscale, and Multiplex Networks
Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., & Onnela, J.-P. (2010) · Science · doi:10.1126/science.1184819 · Cited by 2,123
“ρi|jp ∗ j = ( k i m k j kj + k i m k j kj ) kj 2m = k i k out j + k out i k in j 2m2 , (7)”
Community detection in networks: a user guide
Fortunato, S., & Hric, D. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.09.002 · Cited by 2,086
“Girvan and Newman [8] set q = 4, nc = 32 (for a total number of vertices n = 128) and fixed the average total degree ⟨k⟩ to 16.”
BackgroundMethodInfluentialComputing Communities in Large Networks Using Random Walks
Pons, P., & Latapy, M. (2005) · Lecture Notes in Computer Science · doi:10.1007/11569596_31 · Cited by 2,048
Statistical mechanics of community detection
Reichardt, J., & Bornholdt, S. (2006) · Physical Review E · doi:10.1103/physreve.74.016110 · Cited by 2,048
Detecting community structure in networks
Newman, M. E. J. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00124-y · Cited by 2,028
“We start by describing the algorithm of Girvan and New-man [1], which divides networks by iterative removal of their edges, and some variations on it that have been proposed by other authors.”
BackgroundMethodInfluentialSelf-citationLink communities reveal multiscale complexity in networks
Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010) · Nature · doi:10.1038/nature09182 · Cited by 1,949
Detecting the overlapping and hierarchical community structure in complex networks
Lancichinetti, A., Fortunato, S., & Kertész, J. (2009) · New Journal of Physics · doi:10.1088/1367-2630/11/3/033015 · Cited by 1,941
Coauthorship networks and patterns of scientific collaboration
Newman, M. E. J. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0307545100 · Cited by 1,931
“scientific collaboration”
Self-citationStructure and tie strengths in mobile communication networks
Onnela, J.-P., Saramäki, J., Hyvönen, J., Szabó, G., Lazer, D., Kaski, K., Kertész, J., & Barabási, A.-L. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0610245104 · Cited by 1,926
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,872
“We have tried a number of them, including Graclus [54] and Newman’s modularity optimizing program (we refer to it as Dendrogram) [80].”
BackgroundMethodInfluentialPredicting missing links via local information
Zhou, T., Lü, L., & Zhang, Y.-C. (2009) · The European Physical Journal B · doi:10.1140/epjb/e2009-00335-8 · Cited by 1,813
Group formation in large social networks: membership, growth, and evolution
Backstrom, L., Huttenlocher, D., Kleinberg, J., & Lan, X. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150412 · Cited by 1,805
“, [14, 15, 16, 20, 28]), si nce for us the relevant communities have been identified by the membe rs themselves.”
BackgroundDynamic reconfiguration of human brain networks during learning
Bassett, D. S., Wymbs, N. F., Porter, M. A., Mucha, P. J., Carlson, J. M., & Grafton, S. T. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1018985108 · Cited by 1,705
Schaeffer, S. E. (2007) · Computer Science Review · doi:10.1016/j.cosrev.2007.05.001 · Cited by 1,639
Networks beyond pairwise interactions: Structure and dynamics
Battiston, F., Cencetti, G., Iacopini, I., Latora, V., Lucas, M., Patania, A., Young, J.-G., & Petri, G. (2020) · Physics Reports · doi:10.1016/j.physrep.2020.05.004 · Cited by 1,602
“In this Section, we discuss how coupled dynamical systems can be extended to higher-order systems (HOrSs), and how the presence of high-order interactions can affect synchronization in both phase oscillators and nonlinear dynamical systems.”
BackgroundInfluentialCommunity detection in complex networks using extremal optimization
Duch, J., & Arenas, A. (2005) · Physical Review E · doi:10.1103/physreve.72.027104 · Cited by 1,549
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
“To do so we use the algorithm proposed recently by Girvan and Newman (GN) [9] to identify communities in complex networks (see Fig.”
MethodComputing Communities in Large Networks Using Random Walks
Pons, P., & Latapy, M. (2006) · Journal of Graph Algorithms and Applications · doi:10.7155/jgaa.00124 · Cited by 1,501
Bodin, Ö., & Crona, B. I. (2009) · Global Environmental Change · doi:10.1016/j.gloenvcha.2009.05.002 · Cited by 1,486
“Granovetter, 1973; Newman and Dale, 2007; Lin, 2002), both of which are vital for resource governance. The value of bridging ties has been shown in several disciplines. In organizational science, Ruef (2002) explicitly showed that increased connectivity between different subunits in corporations enhanced productivity…”
BackgroundProtein complexes and functional modules in molecular networks
Spirin, V., & Mirny, L. A. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2032324100 · Cited by 1,461
Defining and evaluating network communities based on ground-truth
Yang, J., & Leskovec, J. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-013-0693-z · Cited by 1,411
“Nodes in such networks organize into densely linked groups that are commonly referred to as network communities , clusters or modules [11].”
BackgroundWhy social networks are different from other types of networks
Newman, M. E. J., & Park, J. (2003) · Physical Review E · doi:10.1103/physreve.68.036122 · Cited by 1,354
“One possibility is suggested by the analysis of the directorships data by Newman et al. [13], who found that directors who sit on many boards tend to sit on them with others who sit on many boards.”
BackgroundMethodInfluentialSelf-citationSporns, O., & Betzel, R. F. (2016) · Annual Review of Psychology · doi:10.1146/annurev-psych-122414-033634 · Cited by 1,334
“These methods include divisive algorithms (Girvan & Newman 2002), spectral decomposition (Newman 2004), extremal optimization (Duch & Arenas 2005), greedy algorithms (Blondel et al. 2008, Clauset et al. 2004), and simulated annealing (Guimera & Amaral 2005), among others.”
MethodCui, P., Wang, X., Pei, J., & Zhu, W. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2849727 · Cited by 1,274
Valente, T. W. (2012) · Science · doi:10.1126/science.1217330 · Cited by 1,271
Subgraph centrality in complex networks
Estrada, E., & Rodríguez-Velázquez, J. A. (2005) · Physical Review E · doi:10.1103/physreve.71.056103 · Cited by 1,260
Networks formed from interdependent networks
Gao, J., Buldyrev, S. V., Stanley, H. E., & Havlin, S. (2012) · Nature Physics · doi:10.1038/nphys2180 · Cited by 1,216
“Networkconcepts have also proven to be useful for the analysis and understanding of the spread of epidemics 57,58 , and the organizational laws of social interactions, such as friendships 59,60 or scientific collaborations 61,62 .”
BackgroundScale-free networks in cell biology
Albert, R. (2005) · Journal of Cell Science · doi:10.1242/jcs.02714 · Cited by 1,215
“Several methods have been proposed to identify functional modules on the basis of the physical location or function of network components (Rives and Galitski, 2003) or the topology of the interaction network (Giot et al., 2003; Girvan and Newman, 2002; Spirin and Mirny, 2003).”
MethodTwo independent modes of chromatin organization revealed by cohesin removal
Schwarzer, W., Abdennur, N., Goloborodko, A., Pekowska, A., Fudenberg, G., Loe-Mie, Y., Fonseca, N. A., Huber, W., Haering, C. H., Mirny, L., et al. (2017) · Nature · doi:10.1038/nature24281 · Cited by 1,196
Finding Statistically Significant Communities in Networks
Lancichinetti, A., Radicchi, F., Ramasco, J. J., & Fortunato, S. (2011) · PLoS ONE · doi:10.1371/journal.pone.0018961 · Cited by 1,187
“Tests on the well known Girvan-Newman (GN) benchmark [8] are shown in the Supporting Information S1.”
Fast Random Walk with Restart and Its Applications
Tong, H., Faloutsos, C., & Pan, J.-Y. (2006) · Sixth International Conference on Data Mining (ICDM'06) · doi:10.1109/icdm.2006.70 · Cited by 1,184
Vital nodes identification in complex networks
Lü, L., Chen, D., Ren, X.-L., Zhang, Q.-M., Zhang, Y.-C., & Zhou, T. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.06.007 · Cited by 1,183
“Many real networks exhibit community structures [208, 209]—connections within a community are dense while across communities are sparse.”
BackgroundModel for cascading failures in complex networks
Crucitti, P., Latora, V., & Marchiori, M. (2004) · Physical Review E · doi:10.1103/physreve.69.045104 · Cited by 1,167
Watts, D. J. (2004) · Annual Review of Sociology · doi:10.1146/annurev.soc.30.020404.104342 · Cited by 1,163
“As a result, it is possible for a universal cascade (i.e., one affecting the entire population) to be triggered by a random shock that, a priori, is indistinguishable from Network Robustness attention concerns the origins and effects of node”
BackgroundGong, G., He, Y., Concha, L., Lebel, C., Gross, D. W., Evans, A. C., & Beaulieu, C. (2009) · Cerebral Cortex · doi:10.1093/cercor/bhn102 · Cited by 1,112
“In this study, we employed the AAL template (Tzourio-Mazoyer et al. 2002) to parcellate the cerebral cortex into 78 cortical regions (39 for each hemisphere, see Supplementary Table 1), each representing a node of the cortical network.”
MethodValente, T. W. (2010) · Social Networks and Health · doi:10.1093/acprof:oso/9780195301014.003.0010 · Cited by 1,108
Network‐based prediction of protein function
Sharan, R., Ulitsky, I., & Shamir, R. (2007) · Molecular Systems Biology · doi:10.1038/msb4100129 · Cited by 1,074
“Wu and Hu (2005) proposed an algorithm that detects ‘community structures’ (Girvan and Newman, 2002) for a given protein seed, in a network without edge reliabilities.”
BackgroundCooperative Game Theory Approaches for Network Partitioning
Avrachenkov, K. E., Kondratev, A. Y., & Mazalov, V. V. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-62389-4_49 · Cited by 1,073
Hyperbolic geometry of complex networks
Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., & Boguñá, M. (2010) · Physical Review E · doi:10.1103/physreve.82.036106 · Cited by 1,059
Ciric, R., Wolf, D. H., Power, J. D., Roalf, D. R., Baum, G. L., Ruparel, K., Shinohara, R. T., Elliott, M. A., Eickhoff, S. B., Davatzikos, C., et al. (2017) · NeuroImage · doi:10.1016/j.neuroimage.2017.03.020 · Cited by 1,042
“Finally, the modularity quality of the resultant consensus partition was estimated according to an established null model (Girvan and Newman, 2002); the mean of Q values across subjects provided an estimate of the sub-network definition still present in the connectome after de-noising.”
MethodThe Kuramoto model in complex networks
Rodrigues, F. A., Peron, T. K. D., Ji, P., & Kurths, J. (2016) · Physics Reports · doi:10.1016/j.physrep.2015.10.008 · Cited by 1,040
“A possible measure is given by the betweenness centrality [147], i.”
BackgroundInfluentialGLEISER, P. M., & DANON, L. (2003) · Advances in Complex Systems · doi:10.1142/s0219525903001067 · Cited by 1,032
Yu, H., Kim, P. M., Sprecher, E., Trifonov, V., & Gerstein, M. (2007) · PLoS Computational Biology · doi:10.1371/journal.pcbi.0030059 · Cited by 1,014
“More recently, Girvan and Newman proposed that the edges with high betweenness are the ones that are ‘‘ between ’’ highly inter-connected subgraph clusters (i.e., ‘‘ community structures ’’ ); therefore, removing these edges could partition a network [16].”
BackgroundMethodLancichinetti, A., & Fortunato, S. (2009) · Physical Review E · doi:10.1103/physreve.80.016118 · Cited by 1,009
Homophily and contagion are generically confounded in observational social network studies
Shalizi, C. R., & Thomas, A. C. (2011) · Sociological Methods & Research · doi:10.1177/0049124111404820 · Cited by 994
“…inter-connected clusters of nodes, with minimal connection between clusters — has been thoroughly explored in the recent literature (explicitly in Girvan and Newman (2002); Newman and Girvan (2003); Bickel and Chen (2009); Porter et al. (2009); Fortunato (2010), implicitly in much smaller…”
BackgroundHe, Y., Chen, Z., & Evans, A. (2008) · The Journal of Neuroscience · doi:10.1523/jneurosci.0141-08.2008 · Cited by 965
“To evaluate the attack tolerance, we repeated the above processes but removed the nodes and links in decreasing order of their betweenness, respectively [the betweenness of an edge is the number of shortest paths between pairs of other nodes that pass through the edge (Girvan and Newman, 2002); links with high edge be…”
BackgroundComputing and applying trust in web-based social networks
Golbeck, J., & Hendler, J. (2005) · University Libraries (University of Maryland) · Cited by 939
Performance of modularity maximization in practical contexts
Good, B. H., de Montjoye, Y.-A., & Clauset, A. (2010) · Physical Review E · doi:10.1103/physreve.81.046106 · Cited by 937
Social Networks and Health: Models, Methods, and Applications
Valente, T. W. (2010) · doi:10.1093/acprof:oso/9780195301014.001.0001 · Cited by 933
Overlapping community detection in networks: The state-of-the-art and comparative study
Xie, J., Kelley, S., & Szymanski, B. K. (2013) · ACM Computing Surveys · doi:10.1145/2501654.2501657 · Cited by 930
“In the GN benchmark · 15 [Girvan and Newman 2002], equal size communities are embedded into a network for a given expected degree and a given mixing parameter µ that measures the ratio of internal connections to outgoing connections.”
BackgroundEffects of missing data in social networks
Kossinets, G. (2006) · Social Networks · doi:10.1016/j.socnet.2005.07.002 · Cited by 926
Empirical comparison of algorithms for network community detection
Leskovec, J., Lang, K. J., & Mahoney, M. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772755 · Cited by 918
Leicht, E. A., Holme, P., & Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.73.026120 · Cited by 916
Self-citationOrigins of Homophily in an Evolving Social Network
Kossinets, G., & Watts, D. J. (2009) · American Journal of Sociology · doi:10.1086/599247 · Cited by 908
Modularity from fluctuations in random graphs and complex networks
Guimerà, R., Sales-Pardo, M., & Amaral, L. A. N. (2004) · Physical Review E · doi:10.1103/physreve.70.025101 · Cited by 894
Structure and dynamics of molecular networks: A novel paradigm of drug discovery
Csermely, P., Korcsmáros, T., Kiss, H. J. M., London, G., & Nussinov, R. (2013) · Pharmacology & Therapeutics · doi:10.1016/j.pharmthera.2013.01.016 · Cited by 892
“Modules of molecular networks are formed from nodes, which are more densely connected with each other than with their neighborhood (Girvan & Newman, 2002; Fortunato, 2010; Kovács et al., 2010; Koch, 2012; Szalay-Bekő et al., 2012).”
BackgroundWeight-conserving characterization of complex functional brain networks
Rubinov, M., & Sporns, O. (2011) · NeuroImage · doi:10.1016/j.neuroimage.2011.03.069 · Cited by 889
Community Preserving Network Embedding
Wang, X., Cui, P., Wang, J., Pei, J., Zhu, W., & Yang, S. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10488 · Cited by 883
Broido, A. D., & Clauset, A. (2019) · Nature Communications · doi:10.1038/s41467-019-08746-5 · Cited by 875
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.