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 401–500 of 1,049
Sentido de comunidad y potenciación comunitaria
Maya‐Jariego, I. (2004) · APUNTES DE PSICOLOGÍA · doi:10.55414/ap.v22i2.50 · Cited by 256
How can social network analysis improve the study of primate behavior?
Sueur, C., Jacobs, A., Amblard, F., Petit, O., & King, A. J. (2011) · American Journal of Primatology · doi:10.1002/ajp.20915 · Cited by 254
Abbe, E., & Sandon, C. (2015) · 2015 IEEE 56th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.47 · Cited by 254
Defining and Evaluating Network Communities Based on Ground-Truth
Yang, J., & Leskovec, J. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.138 · Cited by 254
Applications, Architectures, and Protocol Design Issues for Mobile Social Networks: A Survey
Kayastha, N., Niyato, D., Wang, P., & Hossain, E. (2011) · Proceedings of the IEEE · doi:10.1109/jproc.2011.2169033 · Cited by 253
Social Media Analytics: An Interdisciplinary Approach and Its Implications for Information Systems
Stieglitz, S., Dang-Xuan, L., Bruns, A., & Neuberger, C. (2014) · Business & Information Systems Engineering · doi:10.1007/s12599-014-0315-7 · Cited by 253
“…SNA might also be useful with different community detection methods and algorithms (e.g., graph theoretical approaches such as the Girvan–Newman algorithm (Girvan and Newman 2002) or other clustering methods such as hierarchical, k-means and fuzzy c-means clustering (Prabhu et al. 2010)).”
BackgroundMethodSpreading dynamics in complex networks
Pei, S., & Makse, H. A. (2013) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2013/12/p12002 · Cited by 252
Patania, A., Petri, G., & Vaccarino, F. (2017) · EPJ Data Science · doi:10.1140/epjds/s13688-017-0114-8 · Cited by 252
“In both cases depicted in (b) the cycle [1, 2, 3, 4, 5, 6] is cordless in the network representation, but only in the bottom case it corresponds to”
BackgroundFarkas, I., Ábel, D., Palla, G., & Vicsek, T. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/180 · Cited by 251
Community Detection on Networks with Ricci Flow
Ni, C.-C., Lin, Y.-Y., Luo, F., & Gao, J. (2019) · Scientific Reports · doi:10.1038/s41598-019-46380-9 · Cited by 250
“nprotein interaction networks [1, 53]. There are a few main ideas. One family of algorithms iteratively remove edges of high ‘centrality’, for example, the edge betweenness centrality as suggested in [14] by Girvan and Newman. The other idea is to use modularity (introduced by Newman and Clauset et al. [4, 7]), which…”
BackgroundMethodInfluentialDynamic architecture of a protein kinase
McClendon, C. L., Kornev, A. P., Gilson, M. K., & Taylor, S. S. (2014) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1418402111 · Cited by 249
“S1), and used the Girvan–Newman algorithm (14) to identify the community structure of the resulting pruned graph.”
MethodInformation cascades in complex networks
Jalili, M., & Perc, M. (2017) · Journal of Complex Networks · doi:10.1093/comnet/cnx019 · Cited by 248
“Networks, extracted from real-world data [6], have been shown to share a number of common structural properties such as a scale-free degree distribution, small-worldness [7], community structure [8] densification and shrinking diameter [9].”
BackgroundHierarchical Block Structures and High-Resolution Model Selection in Large Networks
Peixoto, T. P. (2014) · Physical Review X · doi:10.1103/physrevx.4.011047 · Cited by 248
“It is motivated by the desire to be able to characterize the most salient features in large biological [3–5], technological [6, 7] and social systems [3, 8, 9], such that their building blocks become evident, potentially giving valuable insight into the central aspects governing their function and evolution.”
BackgroundCore-Periphery Structure in Networks
Rombach, M. P., Porter, M. A., Fowler, J. H., & Mucha, P. J. (2014) · SIAM Journal on Applied Mathematics · doi:10.1137/120881683 · Cited by 250
Co-authorship networks: a review of the literature
Kumar, S. (2015) · Aslib Journal of Information Management · doi:10.1108/ajim-09-2014-0116 · Cited by 247
Sybillimit: a near-optimal social network defense against sybil attacks
Yu, H., Gibbons, P. B., Kaminsky, M., & Xiao, F. (2010) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2009.2034047 · Cited by 246
“In fact, social networks are well-known [3, 15, 23, 37] to have groups”
BackgroundApplication of random matrix theory to biological networks
Luo, F., Zhong, J., Yang, Y., Scheuermann, R. H., & Zhou, J. (2006) · Physics Letters A · doi:10.1016/j.physleta.2006.04.076 · Cited by 246
Model of genetic variation in human social networks
Fowler, J. H., Dawes, C. T., & Christakis, N. A. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0806746106 · Cited by 245
Practical Recommendations on Crawling Online Social Networks
Gjoka, M., Kurant, M., Butts, C. T., & Markopoulou, A. (2011) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2011.111011 · Cited by 245
Predicting failures with developer networks and social network analysis
Meneely, A., Williams, L., Snipes, W., & Osborne, J. (2008) · Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering · doi:10.1145/1453101.1453106 · Cited by 245
Simulation of robustness against lesions of cortical networks
Kaiser, M., Martin, R., Andras, P., & Young, M. P. (2007) · European Journal of Neuroscience · doi:10.1111/j.1460-9568.2007.05574.x · Cited by 244
“To provide the corresponding metric for the targeted elimination of connections (edges) from the network, we chose edge betweenness (Girvan & Newman, 2002), that is, the number of shortest paths between all pairs of nodes that pass though the edge.”
BackgroundInfluentialParsimonious Module Inference in Large Networks
Peixoto, T. P. (2013) · Physical Review Letters · doi:10.1103/physrevlett.110.148701 · Cited by 244
Finding the core: Network structure in interbank markets
Veld, D. I. ׳., & van Lelyveld, I. (2014) · Journal of Banking & Finance · doi:10.1016/j.jbankfin.2014.08.006 · Cited by 243
Statistically Validated Networks in Bipartite Complex Systems
Tumminello, M., Miccichè, S., Lillo, F., Piilo, J., & Mantegna, R. N. (2011) · PLoS ONE · doi:10.1371/journal.pone.0017994 · Cited by 242
“Indeed the application of community detection algorithms [20,21], such as Infomap [22], to the statistically validated networks reveal clusters of organisms with a direct biological interpretation in terms of lineage (see Fig.”
MethodCommunity detection in networks by using multiobjective evolutionary algorithm with decomposition
Gong, M., Ma, L., Zhang, Q., & Jiao, L. (2012) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2012.03.021 · Cited by 242
“After that, we adopt the concept of modularity, introduced by Girvan and Newman [3] to assess the quality of a partitioning, to select, among the solutions found, that having the highest value of modularity.”
BackgroundMethodInfluentialCommunity structure and scale-free collections of Erdős-Rényi graphs
Seshadhri, C., Kolda, T. G., & Pinar, A. (2012) · Physical Review E · doi:10.1103/physreve.85.056109 · Cited by 241
A method for finding communities of related genes
Wilkinson, D. M., & Huberman, B. A. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0307740100 · Cited by 241
The entropy of randomized network ensembles
Bianconi, G. (2008) · EPL (Europhysics Letters) · doi:10.1209/0295-5075/81/28005 · Cited by 239
Eigenvector centrality for characterization of protein allosteric pathways
Negre, C. F. A., Morzan, U. N., Hendrickson, H. P., Pal, R., Lisi, G. P., Loria, J. P., Rivalta, I., Ho, J., & Batista, V. S. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1810452115 · Cited by 239
“The edge-betweenness matrix is then used for partitioning the network into communities according to the Girvan–Newman algorithm, which is based on maximizing the modularity Q measure (38, 39).”
MethodAdvanced modularity-specialized label propagation algorithm for detecting communities in networks
Liu, X., & Murata, T. (2010) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2009.12.019 · Cited by 239
Community detection in networks: Structural communities versus ground truth
Hric, D., Darst, R. K., & Fortunato, S. (2014) · Physical Review E · doi:10.1103/physreve.90.062805 · Cited by 238
Graph representation learning: a survey
Chen, F., Wang, Y.-C., Wang, B., & Kuo, C.-C. J. (2020) · APSIPA Transactions on Signal and Information Processing · doi:10.1017/atsip.2020.13 · Cited by 237
“Both vertex classification [40] and link prediction [20] [114] can facilitate community detection [33], [102].”
BackgroundSemantic Networks: Structure and Dynamics
Borge-Holthoefer, J., & Arenas, A. (2010) · Entropy · doi:10.3390/e12051264 · Cited by 237
“It has been observed in many different contexts, including metabolic networks, banking networks or the worldwide flight transportation network [46].”
BackgroundOn community outliers and their efficient detection in information networks
Gao, J., Liang, F., Fan, W., Wang, C., Sun, Y., & Han, J. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835907 · Cited by 236
“In recent years, many methods have been developed to discover clusters or communities in networks [11].”
BackgroundMethodText and Structural Data Mining of Influenza Mentions in Web and Social Media
Corley, C. D., Cook, D. J., Mikler, A. R., & Singh, K. P. (2010) · International Journal of Environmental Research and Public Health · doi:10.3390/ijerph7020596 · Cited by 236
“The general form of this community structure finding algorithm is enumerated below, components remaining in the graph at the end of each iteration are the communities [24]: 1.”
BackgroundSkeleton and Fractal Scaling in Complex Networks
Goh, K.-I., Salvi, G., Kahng, B., & Kim, D. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.018701 · Cited by 236
Human Cancer Protein-Protein Interaction Network: A Structural Perspective
Kar, G., Gursoy, A., & Keskin, O. (2009) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000601 · Cited by 235
“Betweenness is a measure of the total number of shortest paths going through a certain node or edge in the network [69].”
BackgroundNetworKit: A tool suite for large-scale complex network analysis
STAUDT, C. L., SAZONOVS, A., & MEYERHENKE, H. (2016) · Network Science · doi:10.1017/nws.2016.20 · Cited by 235
“The task can be turned into a well-defined though NPhard optimization problem by using community quality measures, first and foremost modularity (Girvan and Newman, 2002).”
BackgroundSmall-world file-sharing communities
Iamnitchi, A., Ripeanu, M., & Foster, I. T. (2004) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2004.1356982 · Cited by 235
Giglietto, F., Righetti, N., Rossi, L., & Marino, G. (2020) · Information, Communication & Society · doi:10.1080/1369118x.2020.1739732 · Cited by 152
“Clustering coe ffi cient (Watts & Strogatz, 1998) measures the degree to which nodes in a network tend to cluster together forming triangles and it has been often associated with the presence of strong community structures (Girvan & Newman, 2002).”
BackgroundThe effect of size heterogeneity on community identification in complex networks
Danon, L., Díaz-Guilera, A., & Arenas, A. (2006) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2006/11/p11010 · Cited by 234
Overlapping Community Detection with Graph Neural NetworksPreprint
Shchur, O., & Günnemann, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.12201 · Cited by 234
“Detecting communities allows us to analyze social networks [14], detect fraud [30], discover functional units of the brain [13], and predict functions of proteins [32].”
BackgroundAchieving Optimal Misclassification Proportion in Stochastic Block ModelsPreprint
Gao, C., Ma, Z., Zhang, A. Y., & Zhou, H. H. (2017) · arXiv (Cornell University) · doi:10.5555/3122009.3153016 · Cited by 234
Why We Twitter: An Analysis of a Microblogging Community
Java, A., Song, X., Finin, T., & Tseng, B. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-00528-2_7 · Cited by 233
“In social network area, Newman and Girvan [31,32] proposed a metric called modularity to measure the strength of the community structure.”
BackgroundDetecting complex network modularity by dynamical clustering
Boccaletti, S., Ivanchenko, M., Latora, V., Pluchino, A., & Rapisarda, A. (2007) · Physical Review E · doi:10.1103/physreve.75.045102 · Cited by 232
Probabilistic models for discovering e-communities
Zhou, D., Manavoglu, E., Li, J., Giles, C. L., & Zha, H. (2006) · Proceedings of the 15th international conference on World Wide Web · doi:10.1145/1135777.1135807 · Cited by 232
“Recent algorithms [6, 14, 2] addressed several problems related to prior knowledge of community size, the precise definition of inter-vertices similarity measure and improved computational efficiency [13].”
BackgroundSpatial heterogeneity and co-occurrence patterns of human mucosal-associated intestinal microbiota
Zhang, Z., Geng, J., Tang, X., Fan, H., Xu, J., Wen, X., Ma, Z. (., & Shi, P. (2014) · The ISME Journal · doi:10.1038/ismej.2013.185 · Cited by 232
Wang, G., Xie, C., & Stanley, E. (2016) · Computational Economics · doi:10.1007/s10614-016-9627-7 · Cited by 232
“The betweenness centrality (BC) of an edge is similar to the definition of BC for a node, i.e., it is the number of shortest paths passing through the edge in the network (Girvan and Newman 2002).”
BackgroundResultInfluentialA review of stochastic block models and extensions for graph clustering
Lee, C., & Wilkinson, D. J. (2019) · Applied Network Science · doi:10.1007/s41109-019-0232-2 · Cited by 231
Attention Models in Graphs: A Survey
Lee, J. B., Rossi, R. A., Kim, S., Ahmed, N. K., & Koh, E. (2019) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3363574 · Cited by 231
Fundamentals of spreading processes in single and multilayer complex networks
de Arruda, G. F., Rodrigues, F. A., & Moreno, Y. (2018) · Physics Reports · doi:10.1016/j.physrep.2018.06.007 · Cited by 231
“This measurement is called betweenness centrality and it quantifies the load as the number of times a node acts as a bridge along the shortest path between two other nodes [28].”
BackgroundCommunity detection in large-scale social networks
Du, N., Wu, B., Pei, X., Wang, B., & Xu, L. (2007) · Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis · doi:10.1145/1348549.1348552 · Cited by 231
“Girvan and Newman have introduced a divisive approach[9][10] which includes the removal of the edges depending on their betweenness values.”
BackgroundInfluentialNeurodevelopmental and neuropsychiatric disorders represent an interconnected molecular system
Cristino, A. S., Williams, S. M., Hawi, Z., An, J.-Y., Bellgrove, M. A., Schwartz, C. E., Costa, L. D. F., & Claudianos, C. (2014) · Molecular Psychiatry · doi:10.1038/mp.2013.16 · Cited by 231
Reticulate Representation of Evolutionary and Functional Relationships between Phage Genomes
Lima-Mendez, G., Van Helden, J., Toussaint, A., & Leplae, R. (2008) · Molecular Biology and Evolution · doi:10.1093/molbev/msn023 · Cited by 231
“…ER graph, every pair of nodes are joined with equal probability; thus, the network formed is homogeneous in nature and suitable as a negative control for estimating the significance of phages with high betweenness values, a feature linked to the network community structure (Girvan and Newman 2002).”
BackgroundSequential algorithm for fast clique percolation
Kumpula, J. M., Kivelä, M., Kaski, K., & Saramäki, J. (2008) · Physical Review E · doi:10.1103/physreve.78.026109 · Cited by 230
Liu, C., Liu, J., & Jiang, Z. (2014) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2014.2305974 · Cited by 230
Social network analysis: organizational implications in tourism management
Valeri, M., & Baggio, R. (2020) · International journal of organizational analysis · doi:10.1108/ijoa-12-2019-1971 · Cited by 230
Signal processing techniques for interpolation in graph structured data
Narang, S. K., Gadde, A., & Ortega, A. (2013) · 2013 IEEE International Conference on Acoustics, Speech and Signal Processing · doi:10.1109/icassp.2013.6638704 · Cited by 229
Network Partition-Based Zonal Voltage Control for Distribution Networks With Distributed PV Systems
Zhao, B., Xu, Z., Xu, C., Wang, C., & Lin, F. (2018) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2017.2648779 · Cited by 229
Core-Periphery Structure in Networks (Revisited)
Rombach, P., Porter, M. A., Fowler, J. H., & Mucha, P. J. (2017) · SIAM Review · doi:10.1137/17m1130046 · Cited by 229
Extraction and Analysis of Fictional Character Networks: A Survey
Labatut, V., & Bost, X. (2019) · ACM Computing Surveys · doi:10.1145/3344548 · Cited by 231
Community Detection in Attributed Graphs: An Embedding Approach
Li, Y., Sha, C., Huang, X., & Zhang, Y. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11274 · Cited by 228
“Communities are widely and naturally existed as functional modules in real-world networks, such as social networks, collaboration networks, and web graphs (Girvan and Newman 2002).”
BackgroundCommunity-diversified influence maximization in social networks
Li, J., Cai, T., Deng, K., Wang, X., Sellis, T., & Xia, F. (2020) · Information Systems · doi:10.1016/j.is.2020.101522 · Cited by 228
“Betweenness based community detection metric was also studied by Girvan and Newman in [11].”
MethodComputational network biology: Data, models, and applications
Liu, C., Ma, Y., Zhao, J., Nussinov, R., Zhang, Y.-C., Cheng, F., & Zhang, Z.-K. (2020) · Physics Reports · doi:10.1016/j.physrep.2019.12.004 · Cited by 227
Brain anatomical networks in early human brain development
Fan, Y., Shi, F., Smith, J. K., Lin, W., Gilmore, J. H., & Shen, D. (2011) · NeuroImage · doi:10.1016/j.neuroimage.2010.07.025 · Cited by 225
Memetic algorithm for community detection in networks
Gong, M., Fu, B., Jiao, L., & Du, H. (2011) · Physical Review E · doi:10.1103/physreve.84.056101 · Cited by 225
Design of a directed molecular network
Ashkenasy, G., Jagasia, R., Yadav, M., & Ghadiri, M. R. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0402674101 · Cited by 225
Statistical Measures for Usage‐Based Linguistics
Gries, S. T., & Ellis, N. C. (2015) · Language Learning · doi:10.1111/lang.12119 · Cited by 224
A transcriptional signature of hub connectivity in the mouse connectome
Fulcher, B. D., & Fornito, A. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1513302113 · Cited by 224
It's who you know: graph mining using recursive structural features
Henderson, K., Gallagher, B., Li, L., Akoglu, L., Eliassi-Rad, T., Tong, H., & Faloutsos, C. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020512 · Cited by 223
“Other local and community-level observations show that degree distributions in many graphs follow power-laws [5, 7, 17, 24] and that graphs exhibit modular structure, with nodes forming groups, and groups within groups [9, 14].”
BackgroundBianconi, G. (2021) · doi:10.1017/9781108770996 · Cited by 223
Opinion leader detection: A methodological review
Bamakan, S. M. H., Nurgaliev, I., & Qu, Q. (2019) · Expert Systems with Applications · doi:10.1016/j.eswa.2018.07.069 · Cited by 223
Learning and Innovative Elements of Strategy Adoption Rules Expand Cooperative Network Topologies
Wang, S., Szalay, M. S., Zhang, C., & Csermely, P. (2008) · PLoS ONE · doi:10.1371/journal.pone.0001917 · Cited by 223
“Girvan M, Newman MEJ (2002) Proc.”
MethodInfluentialSemantic Community Identification in Large Attribute Networks
Wang, X., Jin, D., Cao, X., Yang, L., & Zhang, W. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.9977 · Cited by 223
“We first evaluated SCI on a synthetic network constructed using the widely adopted Newman’s model (Girvan and Newman 2002).”
BackgroundMethodInfluentialDickison, M. E., Magnani, M., & Rossi, L. (2016) · Cambridge University Press eBooks · doi:10.1017/cbo9781139941907 · Cited by 222
Listing All Maximal Cliques in Large Sparse Real-World Graphs
Eppstein, D., Löffler, M., & Strash, D. (2013) · ACM Journal of Experimental Algorithmics · doi:10.1145/2543629 · Cited by 221
“01 football [15] 115 613 8 281 < 0.”
Data-Intensive Text Processing with MapReduce
Lin, J., & Dyer, C. (2010) · Synthesis lectures on human language technologies · doi:10.2200/s00274ed1v01y201006hlt007 · Cited by 221
Assessing the relevance of node features for network structure
Bianconi, G., Pin, P., & Marsili, M. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0811511106 · Cited by 221
“nodes, and a variety of methods have been proposed relying on i) structural properties of the network (betweenness centrality [13], modularity [14], spectral decomposition [15], cliques [16] and hierarchical structure [17]), ii) statistical methods [18] or iii) on processes defined on the network [9, 19].”
MethodUncovering latent structure in valued graphs: A variational approach
Mariadassou, M., Robin, S., & Vacher, C. (2010) · The Annals of Applied Statistics · doi:10.1214/10-aoas361 · Cited by 220
“A natural and intuitive way to capture an underlying structure is to look for groups of edges having similar connection profiles [Getoor and Diehl (2004), Newman, Watts and Strogatz (2002)], which is refereed to as community detection [Girvan and Newman (2002), Newman (2004)].”
BackgroundMethodStochastic blockmodels with a growing number of classes
Choi, D. S., Wolfe, P. J., & Airoldi, E. M. (2012) · Biometrika · doi:10.1093/biomet/asr053 · Cited by 220
NetworkView: 3D display and analysis of protein·RNA interaction networks
Eargle, J., & Luthey-Schulten, Z. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts546 · Cited by 220
Computing communities in large networks using random walks (long version)Preprint
Pons, P., & Latapy, M. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.physics/0512106 · Cited by 226
Impact of social network structure on content propagation: A study using YouTube data
Yoganarasimhan, H. (2012) · Quantitative Marketing and Economics · doi:10.1007/s11129-011-9105-4 · Cited by 219
It’s not all about autism: The emerging landscape of anti-vaccination sentiment on Facebook
Hoffman, B. L., Felter, E. M., Chu, K.-H., Shensa, A., Hermann, C., Wolynn, T., Williams, D., & Primack, B. A. (2019) · Vaccine · doi:10.1016/j.vaccine.2019.03.003 · Cited by 218
Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
Emmons, S., Kobourov, S., Gallant, M., & Börner, K. (2016) · PLOS ONE · doi:10.1371/journal.pone.0159161 · Cited by 218
Adaptive algorithms for detecting community structure in dynamic social networks
Nguyen, N. P., Dinh, T. N., Xuan, Y., & Thai, M. T. (2011) · 2011 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2011.5935045 · Cited by 218
“Many social networks exhibit the property of containing community structure [ 1 ][2], i.e., they naturally divide into groups of vertices with denser connections inside each group and fewer connections crossing groups, where vertices and connections represent network users and their social interactions, respectively.”
BackgroundToivonen, R., Onnela, J.-P., Saramäki, J., Hyvönen, J., & Kaski, K. (2006) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2006.03.050 · Cited by 218
Italian tourism intermediaries: a social network analysis exploration
Valeri, M., & Baggio, R. (2021) · Current Issues in Tourism · doi:10.1080/13683500.2020.1777950 · Cited by 218
“The modularity rate can be measured either for a given allotment of the network into modules, or by applying a stochastic calculation that will obtain the breakdown maximizing Q for the network (Clauset et al., 2004; Girvan & Newman, 2002).”
BackgroundGraph Neural Network for Fraud Detection via Spatial-Temporal Attention
Cheng, D., Wang, X., Zhang, Y., & Zhang, L. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3025588 · Cited by 217
Prospects of modelling societal transitions: Position paper of an emerging community
Holtz, G., Alkemade, F., de Haan, F., Köhler, J., Trutnevyte, E., Luthe, T., Halbe, J., Papachristos, G., Chappin, E., Kwakkel, J., et al. (2015) · Environmental Innovation and Societal Transitions · doi:10.1016/j.eist.2015.05.006 · Cited by 216
“…systems share universal characteristics such as scale-freeness, small-world properties, community structure, and degree correlations which can influence the dynamics of the respective system (Cohen and Havlin, 2010; Watts and Strogatz, 1998; Barabási and Albert, 1999; Girvan and Newman, 2002).”
BackgroundSocial Networks and the Semantic Web
Mika, P. (2005) · IEEE/WIC/ACM International Conference on Web Intelligence (WI'04) · doi:10.1109/wi.2004.10039 · Cited by 216
Principles and Overview of Sampling Methods for Modeling Macromolecular Structure and Dynamics
Maximova, T., Moffatt, R., Ma, B., Nussinov, R., & Shehu, A. (2016) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004619 · Cited by 216
“While MD and enhanced versions of MDbased methods are used for the simulations, the analysis is conducted with normal mode analysis (NMA) [228–230], correlation matrices [231–233], community-network analysis [234], mutual information [235], and dynamical network analysis [236–238].”
MethodFortunato, S., & Castellano, C. (2012) · Computational Complexity · doi:10.1007/978-1-4614-1800-9_33 · Cited by 215
A Survey on Controller Placement in SDN
Das, T., Sridharan, V., & Gurusamy, M. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2935453 · Cited by 215
“Aokiand Shinomiya [112] extends [101] by proposing four clustering algorithms (conductance, spectral [155], edge betweenness centrality [156] and repeated bisection [157]) to partition an SDN with the objective of controller load balancing, i.e., minimizing the root mean square deviation of sum of…”
BackgroundEffective community search over large spatial graphs
Fang, Y., Cheng, R., Li, X., Luo, S., & Hu, J. (2017) · Proceedings of the VLDB Endowment · doi:10.14778/3055330.3055337 · Cited by 214
Embodiment and the inner lifeCognition and Consciousness in the Space of Possible Minds
Shanahan, M. (2010) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199226559.001.0001 · Cited by 155
The Potential of Automatic Word Comparison for Historical Linguistics
List, J., Greenhill, S. J., & Gray, R. D. (2017) · PLoS ONE · doi:10.1371/journal.pone.0170046 · Cited by 215
“…List et al. [53] in testing a partitioning approach which was originally developed for the task of community detection in social network analysis [59] and has shown to perform with a high accuracy: The Infomap algorithm [33] uses random walks to identify the best way to assign the nodes in a…”
MethodModularity and Extreme Edges of the Internet
Eriksen, K. A., Simonsen, I., Maslov, S., & Sneppen, K. (2003) · Physical Review Letters · doi:10.1103/physrevlett.90.148701 · Cited by 213
Stevens, A. A., Tappon, S. C., Garg, A., & Fair, D. A. (2012) · PLoS ONE · doi:10.1371/journal.pone.0030468 · Cited by 213
“Therefore, we focused on network modularity, a statistic reflecting how well an entire network is organized into modules of densely interconnected nodes, but with the modules only sparsely interconnected [29–31].”
BackgroundAllosteric pathways in imidazole glycerol phosphate synthase
Rivalta, I., Sultan, M. M., Lee, N.-S., Manley, G. A., Loria, J. P., & Batista, V. S. (2012) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1120536109 · Cited by 213
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.