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 301–400 of 1,049
Approximating Betweenness Centrality
Bader, D. A., Kintali, S., Madduri, K., & Mihail, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-77004-6_10 · Cited by 340
“For instance, the Girvan-Newman [14] algorithm iteratively partitions a network by identifying edges with high betweenness scores, removing them and recomputing centrality scores.”
MethodA survey of community search over big graphs
Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., & Lin, X. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00556-x · Cited by 339
Kovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
Modularity-maximizing graph communities via mathematical programming
Agarwal, G., & Kempe, D. (2008) · The European Physical Journal B · doi:10.1140/epjb/e2008-00425-1 · Cited by 338
“Despite multiple recently proposed hierarchical clustering algorithms (e.g., [18, 37, 41]), there is far from general agreement on what objective functions would capture a “good” hierarchical clustering.”
BackgroundMethodInfluentialA Comprehensive Survey on Deep Clustering: Taxonomy, Challenges, and Future Directions
Zhou, S., Xu, H., Zheng, Z., Chen, J., Li, Z., Bu, J., Wu, J. X., Wang, X. Y., Zhu, W., & Ester, M. (2024) · ACM Computing Surveys · doi:10.1145/3689036 · Cited by 339
“8 Recently, efforts has been paid to perform clustering on large volume vision datasets (e.g., ImageNet).”
Rai, V., & Robinson, S. A. (2015) · Environmental Modelling & Software · doi:10.1016/j.envsoft.2015.04.014 · Cited by 335
Graph-Based Semi-Supervised Learning: A Comprehensive Review
Song, Z., Yang, X., Xu, Z., & King, I. (2023) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3155478 · Cited by 334
Multilayer Networks: Structure and Function
Bianconi, G. (2018) · doi:10.1093/oso/9780198753919.001.0001 · Cited by 334
Automated Network Analysis Identifies Core Pathways in Glioblastoma
Cerami, E., Demir, E., Schultz, N., Taylor, B. S., & Sander, C. (2010) · PLoS ONE · doi:10.1371/journal.pone.0008918 · Cited by 333
Social Network Analysis for Program Implementation
Valente, T. W., Palinkas, L. A., Czaja, S., Chu, K.-H., & Brown, C. H. (2015) · PLOS ONE · doi:10.1371/journal.pone.0131712 · Cited by 332
Comparing Community Structure to Characteristics in Online Collegiate Social Networks
Red, V., Kelsic, E. D., Mucha, P. J., & Porter, M. A. (2011) · SIAM Review · doi:10.1137/080734315 · Cited by 331
“In addition to remarkable successes on benchmark examples, investigations of community structure have led to success stories in diverse application areas— including the reconstruction of college football conferences [11] and the investigation of such structures in algorithmic rankings [6]; the analysis of committee as…”
BackgroundKnowledge transfer via multiple model local structure mapping
Gao, J., Fan, W., Jiang, J., & Han, J. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401928 · Cited by 330
Size reduction of complex networks preserving modularity
Arenas, A., Duch, J., Fernández, A., & Gómez, S. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/176 · Cited by 330
“Here we propose an exact method for reducing the size of weighted (directed and undirected) complex networks while maintaining invariant its modularity.”
MethodDetecting communities in large networks
Capocci, A., Servedio, V. D. P., Caldarelli, G., & Colaiori, F. (2005) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2004.12.050 · Cited by 329
Camacho, D., Panizo-LLedot, Á., Bello-Orgaz, G., Gonzalez-Pardo, A., & Cambria, E. (2020) · Information Fusion · doi:10.1016/j.inffus.2020.05.009 · Cited by 329
Interchange of entire communities: microbial community coalescence
Rillig, M. C., Antonovics, J., Caruso, T., Lehmann, A., Powell, J. R., Veresoglou, S. D., & Verbruggen, E. (2015) · Trends in Ecology & Evolution · doi:10.1016/j.tree.2015.06.004 · Cited by 328
Map-based models in neuronal dynamics
Ibarz, B., Casado, J. M., & Sanjuán, M. A. F. (2011) · Physics Reports · doi:10.1016/j.physrep.2010.12.003 · Cited by 328
E-Mail as Spectroscopy: Automated Discovery of Community Structure within Organizations
Tyler, J. R., Wilkinson, D. M., & Huberman, B. A. (2005) · The Information Society · doi:10.1080/01972240590925348 · Cited by 327
“We describe an experiment performed within our own organization, HP Labs, using nearly one million email messages collected over a period of roughly two months.”
BackgroundMethodInfluentialSocial ties and their relevance to churn in mobile telecom networks
Dasgupta, K., Singh, R., Viswanathan, B., Chakraborty, D., Mukherjea, S., Nanavati, A. A., & Joshi, A. (2008) · Proceedings of the 11th international conference on Extending database technology: Advances in database technology · doi:10.1145/1353343.1353424 · Cited by 326
“Some interesting time-varying properties, related to densification and diameter shrinkage, have been observed for a number of real-world social networks [18], There has been a considerable amount of work devoted to finding (connected) communities in graphs [6,9].”
BackgroundAnalysis and Visualization of Network Data using JUNG
O’Madadhain, J., Fisher, D., Smyth, P., & Boey, Y.-B. (2005) · Cited by 324
Subgraph centrality and clustering in complex hyper-networks
Estrada, E., & Rodríguez-Velázquez, J. A. (2006) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2005.12.002 · Cited by 323
A review of emerging trends in global PPP research: analysis and visualization
Song, J., Zhang, H., & Dong, W. (2016) · Scientometrics · doi:10.1007/s11192-016-1918-1 · Cited by 323
“Such nodes can be used to separate clusters in a network (Girvan and Newman 2002) and to identify potentially revolutionary scientific publications (Chen 2006).”
BackgroundMicrobial diversity and ecological networks as indicators of environmental quality
Karimi, B., Maron, P. A., Chemidlin-Prevost Boure, N., Bernard, N., Gilbert, D., & Ranjard, L. (2017) · Environmental Chemistry Letters · doi:10.1007/s10311-017-0614-6 · Cited by 323
“• the transitivity is the probability that two nodes are both directly and indirectly, i.e. using another node, con- nected (Girvan and Newman 2002).”
BackgroundMining communities and their relationships in blogs: A study of online hate groups
Chau, M., & Xu, J. (2007) · International Journal of Human-Computer Studies · doi:10.1016/j.ijhcs.2006.08.009 · Cited by 323
Dai, E., Zhao, T., Zhu, H., Xu, J., Guo, Z., Liu, H., Tang, J., & Wang, S. (2024) · Machine Intelligence Research · doi:10.1007/s11633-024-1510-8 · Cited by 325
Using network science to evaluate exercise-associated brain changes in older adults.
Burdette (2010) · Frontiers in Aging Neuroscience · doi:10.3389/fnagi.2010.00023 · Cited by 320
“Modularity analyses allow the discovery of community structure within a network, as they show communities in which the nodes are more connected to each other than with nodes in other communities (Girvan and Newman, 2002).”
A Study of the Relationship between Student Social Networks and Sense of Community.
Dawson, S. (2008) · Adelaide Research & Scholarship (AR&S) (University of Adelaide) · Cited by 319
Galpern, P., Manseau, M., & Fall, A. (2011) · Biological Conservation · doi:10.1016/j.biocon.2010.09.002 · Cited by 318
Identification of Essential Proteins Based on Edge Clustering Coefficient
Wang, J., Li, M., Wang, H., & Pan, Y. (2012) · IEEE/ACM Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2011.147 · Cited by 318
Graph Spectra and the Detectability of Community Structure in Networks
Nadakuditi, R. R., & Newman, M. E. J. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.188701 · Cited by 316
Self-citationThe metabolic world of Escherichia coli is not small
Arita, M. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0306458101 · Cited by 315
Chen, B., Li, J. S., Wu, X. F., Han, M. Y., Zeng, L., Li, Z., & Chen, G. Q. (2018) · Applied Energy · doi:10.1016/j.apenergy.2017.10.113 · Cited by 315
Plant Trait Networks: Improved Resolution of the Dimensionality of Adaptation
He, N., Li, Y., Liu, C., Xu, L., Li, M., Zhang, J., He, J., Tang, Z., Han, X., Ye, Q., et al. (2020) · Trends in Ecology & Evolution · doi:10.1016/j.tree.2020.06.003 · Cited by 315
LinkBench: a database benchmark based on the Facebook social graph
Armstrong, T. G., Ponnekanti, V., Borthakur, D., & Callaghan, M. (2013) · Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2463676.2465296 · Cited by 313
Mitigating head motion artifact in functional connectivity MRI
Ciric, R., Rosen, A. F. G., Erus, G., Cieslak, M., Adebimpe, A., Cook, P. A., Bassett, D. S., Davatzikos, C., Wolf, D. H., & Satterthwaite, T. D. (2018) · Nature Protocols · doi:10.1038/s41596-018-0065-y · Cited by 311
A New Measure of Centrality for Brain Networks
Joyce, K. E., Laurienti, P. J., Burdette, J. H., & Hayasaka, S. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012200 · Cited by 310
“The presence of these highly interconnected communities has been termed ‘‘community structure’’ [14,24,33,34,35].”
BackgroundMethodImproving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
Bouritsas, G., Frasca, F., Zafeiriou, S., & Bronstein, M. M. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2022.3154319 · Cited by 309
Neighborhood Formation and Anomaly Detection in Bipartite Graphs
Sun, J., Qu, H., Chakrabarti, D., & Faloutsos, C. (2006) · Fifth IEEE International Conference on Data Mining (ICDM'05) · doi:10.1109/icdm.2005.103 · Cited by 308
The Rise and Fall of Small Worlds: Exploring the Dynamics of Social Structure
Gulati, R., Sytch, M., & Tatarynowicz, A. (2012) · Organization Science · doi:10.1287/orsc.1100.0592 · Cited by 306
SELKOE, K. A., WATSON, J. R., WHITE, C., HORIN, T. B., IACCHEI, M., MITARAI, S., SIEGEL, D. A., GAINES, S. D., & TOONEN, R. J. (2010) · Molecular Ecology · doi:10.1111/j.1365-294x.2010.04658.x · Cited by 305
“Multi-locus estimates of observed heterozygosity (HO), expected heterozygosity (HE), inbreeding coefficients (FIS), rarefied allelic richness (AR) and Weir and Cockerham’s (1984) estimate of FST (h) were calculated with FSTAT (Goudet 1995). RecodeData (Meirmans 2006) was used to standardize multi-locus h values by max…”
MethodBrain networks under attack: robustness properties and the impact of lesions
Aerts, H., Fias, W., Caeyenberghs, K., & Marinazzo, D. (2016) · Brain · doi:10.1093/brain/aww194 · Cited by 304
“The modular structure can be revealed by subdividing the network into modules by maximizing the number of within-group links and minimizing the number of between-group links (Girvan and Newman, 2002; Guimerà and Amaral, 2005).”
BackgroundThe immunoregulatory landscape of human tuberculosis granulomas
McCaffrey, E. F., Donato, M., Keren, L., Chen, Z., Delmastro, A., Fitzpatrick, M. B., Gupta, S., Greenwald, N. F., Baranski, A., Graf, W., et al. (2022) · Nature Immunology · doi:10.1038/s41590-021-01121-x · Cited by 304
An Algorithm to Find Overlapping Community Structure in Networks
Gregory, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74976-9_12 · Cited by 302
“Probably the best-known algorithm for finding community structure is Girvan and Newman’s algorithm [6, 14], based on the betweenness centrality measure [5].”
BackgroundMethodInfluentialFast community detection by SCORE
Jin, J. (2015) · The Annals of Statistics · doi:10.1214/14-aos1265 · Cited by 302
Fitness benefits of coalitionary aggression in male chimpanzees
Gilby, I. C., Brent, L. J. N., Wroblewski, E. E., Rudicell, R. S., Hahn, B. H., Goodall, J., & Pusey, A. E. (2013) · Behavioral Ecology and Sociobiology · doi:10.1007/s00265-012-1457-6 · Cited by 301
“A potential proximate explanation of how high betweenness in the coalition network could lead to high rank and to the production of offspring is that to avoid jeopardizing long-term relationships, males may refrain from forming coalitions against those with whom they share many partners (Girvan and Newman 2002).”
BackgroundCommunity Detection via Maximization of Modularity and Its Variants
Chen, M., Kuzmin, K., & Szymanski, B. K. (2014) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2014.2307458 · Cited by 301
“In this section, we first evaluate the performance ofGreedy , Fine-tuned , and Fine-tuned on two small networks (Zachary’s karate club network [52] and American college football network [53]) with ground truth communities, and then on two large networks [pretty-good-privacy (PGP) network [54] and autonomous system (AS…”
MethodIsayev, O., Fourches, D., Muratov, E. N., Oses, C., Rasch, K., Tropsha, A., & Curtarolo, S. (2015) · Chemistry of Materials · doi:10.1021/cm503507h · Cited by 300
“[62] M.”
BackgroundOptimal Network Modularity for Information Diffusion
Nematzadeh, A., Ferrara, E., Flammini, A., & Ahn, Y.-Y. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.088701 · Cited by 300
Community detection in node-attributed social networks: A survey
Chunaev, P. (2020) · Computer Science Review · doi:10.1016/j.cosrev.2020.100286 · Cited by 300
“According to [76], communities are thought as subsets of nodes with dense connections within the subsets and sparse in between.”
BackgroundNeumeyer, X., & Santos, S. C. (2018) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2017.08.216 · Cited by 299
Improving tourism destination governance: a complexity science approach
Baggio, R., Scott, N., & Cooper, C. (2010) · Tourism Review · doi:10.1108/16605371011093863 · Cited by 298
Bayesian Approach to Network Modularity
Hofman, J. M., & Wiggins, C. H. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.258701 · Cited by 298
The Social Regulation of Emotion: An Integrative, Cross-Disciplinary Model
Reeck, C., Ames, D. R., & Ochsner, K. N. (2016) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2015.09.003 · Cited by 298
Resilience of public transport networks against attacks
Berche, B., von Ferber, C., Holovatch, T., & Holovatch, Y. (2009) · The European Physical Journal B · doi:10.1140/epjb/e2009-00291-3 · Cited by 296
Metrics for Community Analysis: A Survey
Chakraborty, T., Dalmia, A., Mukherjee, A., & Ganguly, N. (2018) · ACM Computing Surveys · doi:10.1145/3091106 · Cited by 296
“Although community is an ill-defined concept [43], a general consensus suggests that community structure is a decomposition of nodes into groups, where within a group nodes are highly connected, and across groups nodes are loosely connected [49].”
BackgroundInfluentialBayesian Stochastic Blockmodeling
Peixoto, T. P. (2019) · Wiley eBooks · doi:10.1002/9781119483298.ch11 · Cited by 299
“Bayesian inference of the SBM for a network of American college football teams [48]: (a) The partition that maximizes the posterior probability of Eq.”
MethodMachine Learning for Sociology
Molina, M., & Garip, F. (2019) · Annual Review of Sociology · doi:10.1146/annurev-soc-073117-041106 · Cited by 295
A Survey of Social-Based Routing in Delay Tolerant Networks: Positive and Negative Social Effects
Zhu, Y., Xu, B., Shi, X., & Wang, Y. (2013) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2012.032612.00004 · Cited by 295
“In [44], Newman proposed a modularity-based community detecting algorithm which uses the metric of quality function " modularity " .”
MethodAssessment of network module identification across complex diseases
The DREAM Module Identification Challenge Consortium, Choobdar, S., Ahsen, M. E., Crawford, J., Tomasoni, M., Fang, T., Lamparter, D., Lin, J., Hescott, B., Hu, X., et al. (2019) · Nature Methods · doi:10.1038/s41592-019-0509-5 · Cited by 294
Method to find community structures based on information centrality
Fortunato, S., Latora, V., & Marchiori, M. (2004) · Physical Review E · doi:10.1103/physreve.70.056104 · Cited by 294
“Recently,Girvan and Newman have considered two forms of edge betweenness to measure the edge importance: the shortest path betweenness and the random-walk be-tweenness [17, 18, 19].”
BackgroundMethodInfluentialCommunity-Affiliation Graph Model for Overlapping Network Community Detection
Yang, J., & Leskovec, J. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.139 · Cited by 293
Ernstson, H., Sörlin, S., & Elmqvist, T. (2008) · Ecology and Society · doi:10.5751/es-02589-130239 · Cited by 292
“Network segmentation was also found in the Main Component, where a community analysis (Girvan and Newman 2002) revealed a Boating Cluster consisting of all existing boating clubs (N1, N24, N41, N42, N43).”
MethodAn event-based framework for characterizing the evolutionary behavior of interaction graphs
Asur, S., Parthasarathy, S., & Ucar, D. (2009) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1631162.1631164 · Cited by 291
“ASUR, S., UCAR,D., AND PARTHASARATHY, S. 2007.”
BackgroundInfluentialFast shortest path distance estimation in large networks
Potamias, M., Bonchi, F., Castillo, C., & Gionis, A. (2009) · Proceedings of the 18th ACM conference on Information and knowledge management · doi:10.1145/1645953.1646063 · Cited by 291
“Finally, community detection has received interest in physics and sociology [16, 19, 33, 44].”
BackgroundAdversarial Attack and Defense on Graph Data: A Survey
Sun, L., Dou, Y., Yang, C., Zhang, K., Wang, J., Yu, P. S., He, L., & Li, B. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3201243 · Cited by 285
An Overview of Social Networks and Economic Applications
Jackson, M. O. (2011) · Handbook of Social Economics · doi:10.1016/b978-0-444-53187-2.00012-7 · Cited by 285
“For example, Girvan and Newman (2002) developed a popular algorithm that repeatedly deletes links from a network based on finding links that have very high measures of betweenness.”
BackgroundThe Brain as a Complex System: Using Network Science as a Tool for Understanding the Brain
Telesford, Q. K., Simpson, S. L., Burdette, J. H., Hayasaka, S., & Laurienti, P. J. (2011) · Brain Connectivity · doi:10.1089/brain.2011.0055 · Cited by 285
“One of the first methods for community detection was Girvan and Newman's algorithm, which detects communities based on the edge betweenness of nodes (Girvan and Newman, 2002).”
Dynamics-Driven Allostery in Protein Kinases
Kornev, A. P., & Taylor, S. S. (2015) · Trends in Biochemical Sciences · doi:10.1016/j.tibs.2015.09.002 · Cited by 284
“Another study [94] used a community analysis based on the Girvan-Newman algorithm [95] and Mutual Information analysis [96] to study multiple microsecond scale simulations of PKA.”
MethodLocal method for detecting communities
Bagrow, J. P., & Bollt, E. M. (2005) · Physical Review E · doi:10.1103/physreve.72.046108 · Cited by 283
Research fronts in data envelopment analysis
Liu, J. S., Lu, L. Y. Y., & Lu, W.-M. (2016) · Omega · doi:10.1016/j.omega.2015.04.004 · Cited by 281
Spectrum of controlling and observing complex networks
Yan, G., Tsekenis, G., Barzel, B., Slotine, J.-J., Liu, Y.-Y., & Barabási, A.-L. (2015) · Nature Physics · doi:10.1038/nphys3422 · Cited by 279
Börner, K., Sanyal, S., & Vespignani, A. (2007) · Annual Review of Information Science and Technology · doi:10.1002/aris.2007.1440410119 · Cited by 279
Concepts and principles in the analysis of brain networks
Wig, G. S., Schlaggar, B. L., & Petersen, S. E. (2011) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.2010.05947.x · Cited by 278
Quantifying the influence of sociality on population structure in bottlenose dolphins
LUSSEAU, D., WILSON, B., HAMMOND, P. S., GRELLIER, K., DURBAN, J. W., PARSONS, K. M., BARTON, T. R., & THOMPSON, P. M. (2006) · Journal of Animal Ecology · doi:10.1111/j.1365-2656.2005.01013.x · Cited by 278
“We used the Girvan–Newman algorithm to detect community structure within the network (Girvan & Newman 2002; Lusseau & Newman 2004; Newman & Girvan 2004).”
Everton, S. F. (2012) · Cambridge University Press eBooks · doi:10.1017/cbo9781139136877 · Cited by 277
Latent social structure in open source projects
Bird, C., Pattison, D., D'Souza, R., Filkov, V., & Devanbu, P. (2008) · Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering · doi:10.1145/1453101.1453107 · Cited by 276
“But how can organizational structure be discovered in this social network? In 2002, Newman and Girvan introduced a quantitative notion of the community structure of a network, as “the division of network nodes into groups within which the network connections are dense, but between which they are sparser” [25].”
BackgroundCommunity Detection in Complex Networks Using Genetic Algorithms
Tasgin, M., Herdağdelen, A., & Bingol, H. O. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0711.0491 · Cited by 275
Networked discontent: The anatomy of protest campaigns in social media
González-Bailón, S., & Wang, N. (2016) · Social Networks · doi:10.1016/j.socnet.2015.07.003 · Cited by 274
Fast unfolding of community hierarchies in large networks
Blondel, V. D., Guillaume, J., Lambiotte, R., & Lefebvre, E. (2008) · Cited by 274
Prediction of emerging technologies based on analysis of the US patent citation network
Érdi, P., Makovi, K., Somogyvári, Z., Strandburg, K., Tobochnik, J., Volf, P., & Zalányi, L. (2013) · Scientometrics · doi:10.1007/s11192-012-0796-4 · Cited by 273
“(Girvan and Newman 2002; Newman and Girvan 2004) random walks (Pons and Latapy Scientometrics (2013) 95:225–242 233”
BackgroundBianconi, G. (2009) · Physical Review E · doi:10.1103/physreve.79.036114 · Cited by 273
BotGrep: finding P2P bots with structured graph analysis
Nagaraja, S., Mittal, P., Hong, C.-Y., Caesar, M., & Borisov, N. (2010) · University of Birmingham Research Portal (University of Birmingham) · Cited by 273
Distance, dissimilarity index, and network community structure
Zhou, H. (2003) · Physical Review E · doi:10.1103/physreve.67.061901 · Cited by 272
Detecting highly overlapping community structure by greedy clique expansion
Lee, C., Reid, F., McDaid, A. F., & Hurley, N. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1002.1827 · Cited by 271
“By expanding all seeds to encompass the entire graph, and merging them along the way, the algorithm produces a dendrogram similar in some respects to the dendrograms produced by classic agglomerative algorithms such as that of Girvan and Newman [2], but which allows overlap, and in which leaves represent seeds rather…”
BackgroundMethodProtein Contact Networks: An Emerging Paradigm in Chemistry
Di Paola, L., De Ruvo, M., Paci, P., Santoni, D., & Giuliani, A. (2013) · Chemical Reviews · doi:10.1021/cr3002356 · Cited by 269
Triadic closure as a basic generating mechanism of communities in complex networks
Bianconi, G., Darst, R. K., Iacovacci, J., & Fortunato, S. (2014) · Physical Review E · doi:10.1103/physreve.90.042806 · Cited by 268
Characterizing the Community Structure of Complex Networks
Lancichinetti, A., Kivelä, M., Saramäki, J., & Fortunato, S. (2010) · PLoS ONE · doi:10.1371/journal.pone.0011976 · Cited by 267
“This concept of community has been implemented to create classes of benchmark graphs with communities, such as those introduced by Girvan and Newman [11] and the graphs recently designed by Lancichinetti et al.”
Chai, Y., Guo, L., Wang, C., Zhao, Z., Du, X., & Pan, J. (2018) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2018.2813400 · Cited by 265
“Based on the modular index of community detection algorithm [20], the proposed cluster performance index comprehensively considers the electrical distance between nodes and regional voltage regulation capability to ensure that the intracluster voltage violation can be solved by each cluster.”
MethodAn Evolutionary Multiobjective Approach for Community Discovery in Dynamic Networks
Folino, F., & Pizzuti, C. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.131 · Cited by 265
“Lancichinetti et al. [43] proposed a new class of benchmarks (LFR benchmark) that extend the Girvan and Newman benchmark by introducing power law degree distributions and different community size.”
BackgroundDeep Autoencoder-like Nonnegative Matrix Factorization for Community Detection
Ye, F., Chen, C., & Zheng, Z. (2018) · Proceedings of the 27th ACM International Conference on Information and Knowledge Management · doi:10.1145/3269206.3271697 · Cited by 263
“, groups of nodes with dense internal connections and sparse external connections [11].”
BackgroundAnalysis of community structure in networks of correlated data
Gómez, S., Jensen, P., & Arenas, A. (2009) · Physical Review E · doi:10.1103/physreve.80.016114 · Cited by 260
Hierarchy Measure for Complex Networks
Mones, E., Vicsek, L., & Vicsek, T. (2012) · PLoS ONE · doi:10.1371/journal.pone.0033799 · Cited by 259
Communities and Emerging Semantics in Semantic Link Network: Discovery and Learning
Zhuge, H. (2009) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2008.141 · Cited by 259
“Girvan and Newman proposed a divisive algorithm (called the GN algorithm) to select the edges to be removed according to their " edge betweenness " [7], [12], [22], [23], [24], [25], a generalization of the centrality betweenness [11].”
MethodGraph-based Natural Language Processing and Information Retrieval
Mihalcea, R., & Radev, D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511976247 · Cited by 259
Compartments in a marine food web associated with phylogeny, body mass, and habitat structure.
Rezende, E. L., Albert, E. M., Fortuna, M. A., & Bascompte, J. (2009) · Ecology Letters · doi:10.1111/j.1461-0248.2009.01327.x · Cited by 258
Measuring and modeling correlations in multiplex networks
Nicosia, V., & Latora, V. (2015) · Physical Review E · doi:10.1103/physreve.92.032805 · Cited by 258
“This is the reason why a lot of interest has been recently devoted to the study of multiplex networks, i.e. networks in which the same set of nodes can be connected by means of links of qualitatively different type or nature.”
BackgroundMetastable chimera states in community-structured oscillator networks
Shanahan, M. (2010) · Chaos: An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.3305451 · Cited by 257
Fluctuating epidemics on adaptive networks
Shaw, L. B., & Schwartz, I. B. (2008) · Physical Review E · doi:10.1103/physreve.77.066101 · Cited by 257
BRAPH: A graph theory software for the analysis of brain connectivity
Mijalkov, M., Kakaei, E., Pereira, J. B., Westman, E., Volpe, G., & Initiative, F. T. A. D. N. (2017) · PLOS ONE · doi:10.1371/journal.pone.0178798 · Cited by 256
“The extent to which a network can be divided into these communities or modules can be calculated using the modularity, which maximizes the number of edges within communities and minimizes the number of edges between different communities [29].”
BackgroundOverlapping stochastic block models with application to the French political blogosphere
Latouche, P., Birmelé, E., & Ambroise, C. (2011) · The Annals of Applied Statistics · doi:10.1214/10-aoas382 · Cited by 257
“For instance, many proteins, so-called moonlighting proteins, are known to have several functions in the cells [Jeffery (1999)], and actors might belong to several groups of interests [Palla et al. (2005)].”
BackgroundInfluential
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.