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 601–700 of 1,049
Neal, Z. (2014) · Social Networks · doi:10.1016/j.socnet.2014.06.001 · Cited by 184
On community structure in complex networks: challenges and opportunities
Cherifi, H., Palla, G., Szymanski, B. K., & Lu, X. (2019) · Applied Network Science · doi:10.1007/s41109-019-0238-9 · Cited by 184
Characterizing Twitter Discussions About HPV Vaccines Using Topic Modeling and Community Detection
Surian, D., Nguyen, D. Q., Kennedy, G., Johnson, M., Coiera, E., & Dunn, A. G. (2016) · Journal of Medical Internet Research · doi:10.2196/jmir.6045 · Cited by 184
“Traditionally, community detection algorithms produced a hard clustering—where each node belongs to only one community [43-47].”
Communities, knowledge creation, and information diffusion
Lambiotte, R., & Panzarasa, P. (2009) · Journal of Informetrics · doi:10.1016/j.joi.2009.03.007 · Cited by 183
“Other local measures of the topology of the networks include the clustering coefficient, correlations between the degrees of adjacent nodes, etc.”
BackgroundMethodInfluentialThe use of multilayer network analysis in animal behaviour
Finn, K. R., Silk, M. J., Porter, M. A., & Pinter-Wollman, N. (2019) · Animal Behaviour · doi:10.1016/j.anbehav.2018.12.016 · Cited by 183
Khodayar, M., Mohammadi, S., Khodayar, M. E., Wang, J., & Liu, G. (2020) · IEEE Transactions on Sustainable Energy · doi:10.1109/tste.2019.2897688 · Cited by 183
“3 depicts the structure of our graph with 75 nodes and 464 weighted edges clustered into six communities using the Girvan–Newman algorithm [49].”
MethodEnhancing network robustness against malicious attacks
Zeng, A., & Liu, W. (2012) · Physical Review E · doi:10.1103/physreve.85.066130 · Cited by 183
Using Social Network Measures in Wildlife Disease Ecology, Epidemiology, and Management
Silk, M. J., Croft, D. P., Delahay, R. J., Hodgson, D. J., Boots, M., Weber, N. L., & McDonald, R. A. (2016) · BioScience · doi:10.1093/biosci/biw175 · Cited by 183
Defensive Modeling of Fake News Through Online Social Networks
Shrivastava, G., Kumar, P., Ojha, R. P., Srivastava, P. K., Mohan, S., & Srivastava, G. (2020) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2020.3014135 · Cited by 157
“However, the current study concludes that the community is a structure of social contact networks [25], [26] in which nodes have unusual connection and nodes have more connection inside a cluster than that between communities.”
BackgroundOnline social networks: measurement, analysis, and applications to distributed information systems
Druschel, P., & Mislove, A. E. (2009) · Rice Research Repository (Rice University) · Cited by 183
Efficiently inferring community structure in bipartite networks
Larremore, D. B., Clauset, A., & Jacobs, A. Z. (2014) · Physical Review E · doi:10.1103/physreve.90.012805 · Cited by 182
A review of dynamic network models with latent variables
Kim, B., Lee, K. H., Xue, L., & Niu, X. M. (2018) · Statistics Surveys · doi:10.1214/18-ss121 · Cited by 182
“For example, in citation and collaboration networks, such communities could be interpreted as scientific disciplines [39, 58], while the communities in food web networks could be interpreted as ecological subsystems [20].”
BackgroundSun, Z., & Müller, D. (2012) · Environmental Modelling & Software · doi:10.1016/j.envsoft.2012.06.007 · Cited by 183
“In IAMO-LUC, we adopted a community structure for our small-world network (Girvan and Newman, 2002) to account for the multilevel nature of our data with villages and households (Fig.”
MethodEnergy landscape and dynamics of brain activity during human bistable perception
Watanabe, T., Masuda, N., Megumi, F., Kanai, R., & Rees, G. (2014) · Nature Communications · doi:10.1038/ncomms5765 · Cited by 150
AutoPart: Parameter-Free Graph Partitioning and Outlier Detection
Chakrabarti, D. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30116-5_13 · Cited by 180
CIM: Community-Based Influence Maximization in Social Networks
Chen, Y.-C., Zhu, W.-Y., Peng, W.-C., Lee, W.-C., & Lee, S.-Y. (2014) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2532549 · Cited by 180
A Study of Layout, Rendering, and Interaction Methods for Immersive Graph Visualization
Kwon, O.-H., Muelder, C., Lee, K., & Ma, K.-L. (2016) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2016.2520921 · Cited by 180
Maiya, A. S., & Berger-Wolf, T. Y. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772762 · Cited by 180
Community detection via semi-synchronous label propagation algorithms
Cordasco, G., & Gargano, L. (2010) · doi:10.1109/basna.2010.5730298 · Cited by 180
Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
Papadopoulos, F., Krioukov, D., Boguna, M., & Vahdat, A. (2010) · 2010 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2010.5462131 · Cited by 179
Collaboration and cooperation in a tourism destination: a network science approach
Baggio, R. (2011) · Current Issues in Tourism · doi:10.1080/13683500.2010.531118 · Cited by 179
Chen, B., Fan, W., Liu, J., & Wu, F.-X. (2014) · Briefings in Bioinformatics · doi:10.1093/bib/bbt039 · Cited by 179
High quality, scalable and parallel community detection for large real graphs
Prat-Pèrez, A., Domínguez-Sal, D., & Larriba-Pey, J.-L. (2014) · International World Wide Web Conference (WWW) · doi:10.1145/2566486.2568010 · Cited by 180
“Community detection provides valuable information about the structural properties of the network [5, 9], the interactions among the agents of a network [3] or the role the agents develop inside the network [21].”
BackgroundA survey of community detection methods in multilayer networks
Huang, X., Chen, D., Ren, T., & Wang, D. (2021) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-020-00716-6 · Cited by 178
Bridging: Locating critical connectors in a network
Valente, T. W., & Fujimoto, K. (2010) · Social Networks · doi:10.1016/j.socnet.2010.03.003 · Cited by 178
Overlapping community detection via bounded nonnegative matrix tri-factorization
Zhang, Y., & Yeung, D.-Y. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339629 · Cited by 178
“One important problem in understanding the structure of a network is to detect and extract its modular structure consisting of communities, which is often known as community detection [7].”
BackgroundMethodDetection of community structures in networks via global optimization
Medus, A., Acuña, G., & Dorso, C. O. (2005) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2005.04.022 · Cited by 178
How can social network analysis contribute to social behavior research in applied ethology?
Makagon, M. M., McCowan, B., & Mench, J. A. (2012) · Applied Animal Behaviour Science · doi:10.1016/j.applanim.2012.02.003 · Cited by 143
Ollivier-Ricci Curvature-Based Method to Community Detection in Complex Networks
Sia, J., JONCKHEERE, E. A., & Bogdan, P. (2019) · Scientific Reports · doi:10.1038/s41598-019-46079-x · Cited by 178
Quantum Optimization and Quantum Learning: A Survey
Li, Y., Tian, M., Liu, G., Peng, C., & Jiao, L. (2020) · IEEE Access · doi:10.1109/access.2020.2970105 · Cited by 177
Opportunity Spaces in Innovation: Empirical Analysis of Large Samples of Ideas
Kornish, L. J., & Ulrich, K. T. (2011) · Management Science · doi:10.1287/mnsc.1100.1247 · Cited by 177
“Uses of this clustering technique are described in Punj and Stewart (1983), Girvan and Newman (2002), and Gulbahce and Lehmann (2008).”
MethodHuang, S.-S. C., & Fraenkel, E. (2009) · Science Signaling · doi:10.1126/scisignal.2000350 · Cited by 177
Protestant Letter Networks in the Reign of Mary I: A Quantitative Approach
Ahnert, R., & Ahnert, S. E. (2015) · ELH · doi:10.1353/elh.2015.0000 · Cited by 177
Structure and evolution of global cluster networks: evidence from the aerospace industry
Turkina, E., Assche, A. V., & Kali, R. (2016) · Journal of Economic Geography · doi:10.1093/jeg/lbw020 · Cited by 178
An individual-based approach to SIR epidemics in contact networks
Youssef, M., & Scoglio, C. (2011) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2011.05.029 · Cited by 176
“To take into account the heterogeneous contact process in a social context, contact networks [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15], have been considered in modeling epidemics.”
BackgroundNetwork histograms and universality of blockmodel approximation
Olhede, S. C., & Wolfe, P. J. (2014) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1400374111 · Cited by 176
Structural Inference of Hierarchies in Networks
Clauset, A., Moore, C., & Newman, M. E. J. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-73133-7_1 · Cited by 142
“In addition to persistent interest in the sociology community, a number of authors in physics have recently discussed aspects of hierarchical structure [14, 18, 19], although generally via indirect or heuristic means.”
BackgroundInfluentialSelf-citationIdentifying communities within energy landscapes
Massen, C. P., & Doye, J. P. K. (2005) · Physical Review E · doi:10.1103/physreve.71.046101 · Cited by 152
Operationalizing Network Theory for Ecosystem Service Assessments
Dee, L. E., Allesina, S., Bonn, A., Eklöf, A., Gaines, S. D., Hines, J., Jacob, U., McDonald-Madden, E., Possingham, H., Schröter, M., et al. (2017) · Trends in Ecology & Evolution · doi:10.1016/j.tree.2016.10.011 · Cited by 175
Exploring local community structures in large networks
Luo, F., Wang, J. Z., & Promislow, E. (2008) · Web Intelligence and Agent Systems: An International Journal · doi:10.3233/wia-2008-0147 · Cited by 175
Small‐world network approach to identify key residues in protein–protein interaction
del Sol, A., & O'Meara, P. (2005) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.20348 · Cited by 175
Tracking community evolution in social networks: A survey
Dakiche, N., Benbouzid-Si Tayeb, F., Slimani, Y., & Benatchba, K. (2019) · Information Processing & Management · doi:10.1016/j.ipm.2018.03.005 · Cited by 175
Network analysis in conservation biogeography: challenges and opportunities
Cumming, G. S., Bodin, Ö., Ernstson, H., & Elmqvist, T. (2010) · Diversity and Distributions · doi:10.1111/j.1472-4642.2010.00651.x · Cited by 177
“For example, a hierarchical clustering algorithm using the concept of betweenness centrality proposed by Girvan & Newman (2002) has been applied to decomposing a fragmented landscape into different compartments (Bodin & Norberg, 2007).”
MethodSimpson, S. L., Bowman, F. D., & Laurienti, P. J. (2013) · Statistics Surveys · doi:10.1214/13-ss103 · Cited by 175
“Functional brain networks subdivide into interconnected communities (modules) that allow an efficient division of labor [86, 87].”
BackgroundMethodRacial Formation in Perspective: Connecting Individuals, Institutions, and Power Relations
Saperstein, A., Penner, A. M., & Light, R. (2013) · Annual Review of Sociology · doi:10.1146/annurev-soc-071312-145639 · Cited by 149
“Note: Node sizes correspond with times cited; node colors represent communities based on Girvan & Newman (2002); edges correspond with the cosine score based on citation overlap; labels consist of the top-three keywords; label sizes represent the percent of articles in the clusters that cite Omi &…”
BackgroundCommunity detection with the Label Propagation Algorithm: A survey
Garza, S. E., & Schaeffer, S. E. (2019) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2019.122058 · Cited by 176
CDLIB: a python library to extract, compare and evaluate communities from complex networks
Rossetti, G., Milli, L., & Cazabet, R. (2019) · Applied Network Science · doi:10.1007/s41109-019-0165-9 · Cited by 176
A Fast Algorithm to Find Overlapping Communities in Networks
Gregory, S. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-87479-9_45 · Cited by 174
“It extends Girvan and Newman’s [8, 18] algorithm (the “GN algorithm”) with the ability to split vertices between clusters, based on the new concept of split betweenness.”
MethodDetection of Overlapping Communities in Dynamical Social Networks
Cazabet, R., Amblard, F., & Hanachi, C. (2010) · doi:10.1109/socialcom.2010.51 · Cited by 174
Changing Routines: A Process Model of Vicarious Group Learning in Pharmaceutical R&D
Bresman, H. (2013) · Academy of Management Journal · doi:10.5465/amj.2010.0725 · Cited by 173
Fast computation of SimRank for static and dynamic information networks
Li, C., Han, J., He, G., Jin, X., Sun, Y., Yu, Y., & Wu, T. (2010) · Proceedings of the 13th International Conference on Extending Database Technology · doi:10.1145/1739041.1739098 · Cited by 173
“Based on this, we develop a family of novel approximate SimRank computation algorithms for static and dynamic information networks, and give their corresponding theoretical justi.cation and analysis.”
MethodBoolean modeling of biological regulatory networks: A methodology tutorial
Saadatpour, A., & Albert, R. (2012) · Methods · doi:10.1016/j.ymeth.2012.10.012 · Cited by 173
“9 of an edge can be defined similarly [81].”
BackgroundGraph Matching: Relax at Your Own Risk
Lyzinski, V., Fishkind, D. E., Fiori, M., Vogelstein, J. T., Priebe, C. E., & Sapiro, G. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2424894 · Cited by 173
“These graphs have been used to model many real data networks, from the Internet [40], [41], to social and biological networks [42], to name a few.”
MethodData mining of social networks represented as graphs
Nettleton, D. (2013) · Computer Science Review · doi:10.1016/j.cosrev.2012.12.001 · Cited by 174
“[20] M.”
Topic oriented community detection through social objects and link analysis in social networks
Zhao, Z., Feng, S., Wang, Q., Huang, J. Z., Williams, G. J., & Fan, J. (2011) · Knowledge-Based Systems · doi:10.1016/j.knosys.2011.07.017 · Cited by 173
Statistical physics approaches to the complex Earth system
Fan, J., Meng, J., Ludescher, J., Chen, X., Ashkenazy, Y., Kurths, J., Havlin, S., & Schellnhuber, H. J. (2021) · Physics Reports · doi:10.1016/j.physrep.2020.09.005 · Cited by 172
Robust Reconstruction of Complex Networks from Sparse Data
Han, X., Shen, Z., Wang, W.-X., & Di, Z. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.028701 · Cited by 172
The Structure of Borders in a Small World
Thiemann, C., Theis, F., Grady, D., Brune, R., & Brockmann, D. (2010) · PLoS ONE · doi:10.1371/journal.pone.0015422 · Cited by 172
Understanding biological functions through molecular networks
Han, J.-D. J. (2008) · Cell Research · doi:10.1038/cr.2008.16 · Cited by 172
Age‐related changes in topological organization of structural brain networks in healthy individuals
Wu, K., Taki, Y., Sato, K., Kinomura, S., Goto, R., Okada, K., Kawashima, R., He, Y., Evans, A. C., & Fukuda, H. (2012) · Human Brain Mapping · doi:10.1002/hbm.21232 · Cited by 172
The Impact of Imitation on Vaccination Behavior in Social Contact Networks
Ndeffo-Mbah, M. L., Liu, J., Bauch, C. T., Tekel, Y. I., Medlock, J., Ancel, L. W., & Galvani, A. P. (2012) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002469 · Cited by 172
“In reality, there is individual heterogeneity in the number of contacts [9–22] and individuals frequently imitate behaviors of their contacts [23,24], particularly those who appear to have adopted successful strategies [25,26].”
BackgroundEstimating the Number of Communities in a Network
Newman, M. E. J., & Reinert, G. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.078301 · Cited by 172
“The development of algorithmic methods for community detection has been the subject of a large volume of recent research [2–4], as a result of which we now have a number of efficient and sensitive detection techniques that are able to find meaningful communities in real-world settings [4–11].”
MethodSelf-citationJin, D., Liu, Z., Li, W., He, D., & Zhang, W. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.3301152 · Cited by 172
An expert system for detecting automobile insurance fraud using social network analysis
Šubelj, L., Furlan, Š., & Bajec, M. (2011) · Expert Systems with Applications · doi:10.1016/j.eswa.2010.07.143 · Cited by 139
“Girvan & Newman (2002) suggested identifying communities by recursively removing the edges between them – between edges .”
BackgroundMethodInferring social network structure in ecological systems from spatio-temporal data streams
Psorakis, I., Roberts, S. J., Rezek, I., & Sheldon, B. C. (2012) · Journal of The Royal Society Interface · doi:10.1098/rsif.2012.0223 · Cited by 171
“We apply the above scheme on the Newman-Girvan random graph (NG) template [6] that consists of N = 128 nodes, observed solution of C = 4 communities (with n = 32 nodes each) and average degree of 〈k〉 = 16.”
MethodCommunity analysis in social networks
Arenas, A., Danon, L., D�az-Guilera, A., Gleiser, P. M., & Guimer�, R. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00130-1 · Cited by 171
GED: the method for group evolution discovery in social networks
Bródka, P., Saganowski, S., & Kazienko, P. (2013) · Social Network Analysis and Mining · doi:10.1007/s13278-012-0058-8 · Cited by 171
Community extraction for social networks
Zhao, Y., Levina, E., & Zhu, J. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1006642108 · Cited by 171
“lapping or not, every node is required to belong to at least one community. There are many examples of networks where such a requirement makes sense, 1 for example, the college football games network [8], and yet some commonly studied networks clearly do not fit this framework. For example, in the high school friendshi…”
BackgroundExploring Residue Component Contributions to Dynamical Network Models of Allostery
VanWart, A. T., Eargle, J., Luthey-Schulten, Z., & Amaro, R. E. (2012) · Journal of Chemical Theory and Computation · doi:10.1021/ct300377a · Cited by 171
Clement, J., Shipilov, A., & Galunic, C. (2018) · Administrative Science Quarterly · doi:10.1177/0001839217708984 · Cited by 171
“…(M) value, which captures the difference between the ratio of ties within vs. between communities and the ratio that would be expected in a random network of the same size, same degree distribution, and same number of people working across teams (Girvan and Newman, 2002; Porter et al., 2007).”
BackgroundAhmadlou, M., & Adeli, H. (2011) · NeuroImage · doi:10.1016/j.neuroimage.2011.04.070 · Cited by 171
“Analysis of communities among sub-parts of a system is increasingly used for social networks (Girvan and Newman, 2002; Palla et al., 2005; Mann et al., 2008; Chen and Redner, 2010), ecological networks (Tschirhart, 2002; Pusch et al.”
Cascaded failures in weighted networks
Mirzasoleiman, B., Babaei, M., Jalili, M., & Safari, M. (2011) · Physical Review E · doi:10.1103/physreve.84.046114 · Cited by 171
Organization of Group Members at Departure Is Driven by Social Structure in Macaca
Sueur, C., & Petit, O. (2008) · International Journal of Primatology · doi:10.1007/s10764-008-9262-9 · Cited by 171
“…the following standard network properties: mean association, density, and eigenvector centrality coefficient, which we calculated via SOCPROG 2.3 (Girvan and Newman 2002; Newman 2004; Newman and Girvan 2004; Sundaresan et al. 2007; Wasserman and Faust 1994; Whitehead 1997; Whitehead et al. 2005).”
MethodInfluentialOpinion polarization by learning from social feedback
Banisch, S., & Olbrich, E. (2019) · The Journal of Mathematical Sociology · doi:10.1080/0022250x.2018.1517761 · Cited by 106
“In particular, our analysis points at the relevance of community structure of a graph which, in network science, is typically captured by measures of modularity (Fortunato, 2010; Girvan & Newman, 2002).”
BackgroundPersistence and periodicity in a dynamic proximity network
Clauset, A. J., & Eagle, N. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1211.7343 · Cited by 137
Variational Bayesian inference and complexity control for stochastic block models
Latouche, P., Birmelé, E., & Ambroise, C. (2012) · Statistical Modelling · doi:10.1177/1471082x1001200105 · Cited by 169
“Some models look for community structure, also called homophily or assor-tative mixing (Girvan and Newman 2002, Danon et al 2005).”
BackgroundSurvey on Social Community Detection
Plantié, M., & Crampes, M. (2013) · Computer Communications and Networks · doi:10.1007/978-1-4471-4555-4_4 · Cited by 169
Wireless Device-to-Device Communications and Networks
Song, L., Niyato, D. T., Han, Z., & Hossain, E. (2015) · Cambridge University Press eBooks · doi:10.1017/cbo9781107478732 · Cited by 169
Wei, K., Liang, X., & Xu, K. (2013) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2013.042313.00103 · Cited by 169
“Girvan and Newman [54] propose the fist divisive detection algorithm (called GN), which adopts betweenness to extract communities from a number of nodes.”
BackgroundMethodBayesian stochastic blockmodeling
Peixoto, T. P. (2017) · The University of Bath Online Publications Store (The University of Bath) · Cited by 169
Complex-network-based traffic network analysis and dynamics: A comprehensive review
Zhang, M., Huang, T., Guo, Z., & He, Z. (2022) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2022.128063 · Cited by 169
Social Network Analysis: A Survey on Process, Tools, and Application
Singh, S. S., Muhuri, S., Mishra, S., Srivastava, D., Shakya, H. K., & Kumar, N. (2024) · ACM Computing Surveys · doi:10.1145/3648470 · Cited by 169
“By gradually eliminating edges until a new community forms, the Girvan-Newman algorithm discovers community structure in a divisive manner [61].”
BackgroundBetweenness centrality in a weighted network
Wang, H., Martín-Hernández, J., & Mieghem, P. V. (2008) · Physical Review E · doi:10.1103/physreve.77.046105 · Cited by 169
Role of centrality for the identification of influential spreaders in complex networks
de Arruda, G. F., Barbieri, A. L., Rodríguez, P. M., Rodrigues, F. A., Moreno, Y., & Costa, L. D. F. (2014) · Physical Review E · doi:10.1103/physreve.90.032812 · Cited by 168
A simple model of bipartite cooperation for ecological and organizational networks
Saavedra, S., Reed-Tsochas, F., & Uzzi, B. (2009) · Nature · doi:10.1038/nature07532 · Cited by 168
The challenge of predicting distal active site mutations in computational enzyme design
Osuna, S. (2021) · WIREs Computational Molecular Science · doi:10.1002/wcms.1502 · Cited by 168
“Further partitioning of the graph into communities by means of the Girvan – Newman algorithm 113 yields the so-called optimal community network that has been extensively applied for studying allosterically-regulated enzymes.”
MethodMultiresolution Consensus Clustering in Networks
Jeub, L. G. S., Sporns, O., & Fortunato, S. (2018) · Scientific Reports · doi:10.1038/s41598-018-21352-7 · Cited by 168
Multi-Agent Systems and Complex Networks: Review and Applications in Systems Engineering
Herrera, M., Hernández, M. P., Parlikad, A. K., & Izquierdo, J. (2020) · Processes · doi:10.3390/pr8030312 · Cited by 168
Behavioral dynamics of tax evasion – A survey
Pickhardt, M., & Prinz, A. (2014) · Journal of Economic Psychology · doi:10.1016/j.joep.2013.08.006 · Cited by 167
Community structure of the physical review citation network
Chen, P., & Redner, S. (2010) · Journal of Informetrics · doi:10.1016/j.joi.2010.01.001 · Cited by 167
“The journal also includes a letters section, Physical Review Letters (PRL), that was introduced in 1958, a review section, Reviews of Modern Physics (RMP), that was introduced in 1929, and two recent special topics journals.”
BackgroundA measure of individual role in collective dynamics
Klemm, K., Serrano, M. Á., Eguíluz, V. M., & Miguel, M. S. (2012) · Scientific Reports · doi:10.1038/srep00292 · Cited by 167
A Spectral Graph Uncertainty Principle
Agaskar, A., & Lu, Y. M. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2252233 · Cited by 167
“The localization properties of these two construction s are studied on a graph visualized in Figure 7(a) based on the n etwork of football games played in the 2000 regular season by NCAA Division I-A teams [37].”
BackgroundMethodModular organization of protein interaction networks
Luo, F., Yang, Y., Chen, C.-F., Chang, R., Zhou, J., & Scheuermann, R. H. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btl562 · Cited by 167
“Girvan and Newman (2002) proposed the concept of edge betweenness, which is defined as the number of shortest paths between all pairs of vertices that run through the edge.”
BackgroundExploring the Free Energy Landscape: From Dynamics to Networks and Back
Prada-Gracia, D., Gómez-Gardeñes, J., Echenique, P., & Falo, F. (2009) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000415 · Cited by 167
“d henceforth to analyze a specific dynamics of complex systems such as biopolymers. Conformational Markov Network The CMN has been proven to be a useful representation of large stochastic trajectories [10,11,15]. This coarse grained picture is usually constructed by discretizing the conformational space explored by the…”
BackgroundCommunity Detection in Multi-Layer Networks Using Joint Nonnegative Matrix Factorization
Ma, X., Dong, D., & Wang, Q. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2832205 · Cited by 167
“Various networks exist in the real world, such as social networks [1], techno-”
BackgroundA Brief History of Statistical Models for Network Analysis and Open Challenges
Fienberg, S. E. (2012) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.2012.738106 · Cited by 167
“More recently, this style of statistical physics models has been used to detect community structure in networks, for example, see Girvan and Newman (2002) and Backstrom et al. (2006), a phenomenon that has its counterpart description in the social science network modeling literature.”
MethodThe geography of spatial synchrony
Walter, J. A., Sheppard, L. W., Anderson, T. L., Kastens, J. H., Bjørnstad, O. N., Liebhold, A. M., & Reuman, D. C. (2017) · Ecology Letters · doi:10.1111/ele.12782 · Cited by 167
A Tensor Approach to Learning Mixed Membership Community ModelsPreprint
Anandkumar, A., Ge, R., Hsu, D., & Kakade, S. M. (2013) · arXiv (Cornell University) · doi:10.5555/2627435.2670323 · Cited by 167
Emergency information diffusion on online social media during storm Cindy in U.S.
Kim, J., Bae, J., & Hastak, M. (2018) · International Journal of Information Management · doi:10.1016/j.ijinfomgt.2018.02.003 · Cited by 166
An event-based framework for characterizing the evolutionary behavior of interaction graphs
Asur, S., Parthasarathy, S., & Ucar, D. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281290 · Cited by 166
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.