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 901–1,000 of 1,049
Hierarchical Information Clustering by Means of Topologically Embedded Graphs
Song, W., Matteo, T. D., & Aste, T. (2012) · PLoS ONE · doi:10.1371/journal.pone.0031929 · Cited by 138
Uncovering fuzzy community structure in complex networks
Zhang, S., Wang, R., & Zhang, X.-S. (2007) · Physical Review E · doi:10.1103/physreve.76.046103 · Cited by 138
Cross‐sector partnerships: Mapping the field and advancing an institutional approach
Vogel, R., Göbel, M., Grewe‐Salfeld, M., Herbert, B., Matsuo, Y., & Weber, C. (2021) · International Journal of Management Reviews · doi:10.1111/ijmr.12283 · Cited by 138
Sexual dimorphism in the complete Drosophila male central nervous system connectome
Berg, S., Beckett, I. R., Costa, M., Schlegel, P., Januszewski, M., Marin, E. C., Nern, A., Preibisch, S., Qiu, W., Takemura, S.-Y., et al. (2026) · Cell · doi:10.1016/j.cell.2026.08.015 · Cited by 141
Community Structure in GraphsPreprint
Fortunato, S., & Castellano, C. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0712.2716 · Cited by 137
“The most famous computer generated benchmark is a class of graphs designed by Girvan and Newman [14].”
BackgroundMethodInfluentialInfluence of network topology on sound propagation in granular materials
Bassett, D. S., Owens, E. T., Daniels, K. E., & Porter, M. A. (2012) · Physical Review E · doi:10.1103/physreve.86.041306 · Cited by 136
A survey of data mining and social network analysis based anomaly detection techniques
Kaur, R., & Singh, S. (2016) · Egyptian Informatics Journal · doi:10.1016/j.eij.2015.11.004 · Cited by 118
Percolation of heterogeneous flows uncovers the bottlenecks of infrastructure networks
Hamedmoghadam, H., Jalili, M., Vu, H. L., & Stone, L. (2021) · Nature Communications · doi:10.1038/s41467-021-21483-y · Cited by 136
Networks for systems biology: conceptual connection of data and function
Emmert‐Streib, F., & Dehmer, M. (2011) · IET Systems Biology · doi:10.1049/iet-syb.2010.0025 · Cited by 135
Modulated Modularity Clustering as an Exploratory Tool for Functional Genomic Inference
Stone, E. A., & Ayroles, J. F. (2009) · PLoS Genetics · doi:10.1371/journal.pgen.1000479 · Cited by 120
Model Selection and Hypothesis Testing for Large-Scale Network Models with Overlapping Groups
Peixoto, T. P. (2015) · Physical Review X · doi:10.1103/physrevx.5.011033 · Cited by 136
“Examples of this include modularity [12], betweenness [13], link similarity [14], clique percolation [15], encoding of random walks [16], and many more [2].”
BackgroundBlogosphere: research issues, tools, and applications
Agarwal, N. K., & Liu, H. (2008) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1412734.1412737 · Cited by 135
Community detection and graph partitioning
Newman, M. E. J. (2013) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/103/28003 · Cited by 135
“The problem of community detection in networks has received wide attention [1, 2].”
Self-citationHospital Networks and the Dispersal of Hospital-Acquired Pathogens by Patient Transfer
Donker, T., Wallinga, J., Slack, R. C., & Grundmann, H. (2012) · PLoS ONE · doi:10.1371/journal.pone.0035002 · Cited by 135
“To expose the structure of the English hospital referral network, the hospitals were grouped into hospital regional clusters, based on the weights of the connections between all hospitals, mij , using a community detection algorithm [16] which searches for division of the network with the highest modularity Q [31].”
BackgroundMethodLuo, X., Liu, Z., Shang, M., Lou, J., & Zhou, M. (2020) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2020.3040407 · Cited by 135
Networks behind the morphology and structural design of living systems
Gosak, M., Milojević, M., Duh, M., Skok, K., & Perc, M. (2022) · Physics of Life Reviews · doi:10.1016/j.plrev.2022.03.001 · Cited by 135
“Further major breakthroughs include the growth and preferential attachment model that describes the universal scaling in degree distributions by Barabási and Albert [5], and the observation that many networks have groups of nodes that are much stronger connected to one another than to other nodes, which today is well-…”
BackgroundDetecting overlapping communities of weighted networks via a local algorithm
Chen, D., Shang, M., Lv, Z., & Fu, Y. (2010) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.05.046 · Cited by 135
Emergence of Soft Communities from Geometric Preferential Attachment
Zuev, K. M., Boguñá, M., Bianconi, G., & Krioukov, D. (2015) · Scientific Reports · doi:10.1038/srep09421 · Cited by 135
“Nevertheless, PA alone cannot explain two other empirically observed universal properties of complex networks: strong clustering [14] and significant community structure [15].”
BackgroundA Comparison of Social Organization in Asian Elephants and African Savannah Elephants
de Silva, S., & Wittemyer, G. (2012) · International Journal of Primatology · doi:10.1007/s10764-011-9564-1 · Cited by 134
Avoiding a Spanning Cluster in Percolation Models
Cho, Y. S., Hwang, S., Herrmann, H. J., & Kahng, B. (2013) · Science · doi:10.1126/science.1230813 · Cited by 134
Côme, É., & Latouche, P. (2015) · Statistical Modelling · doi:10.1177/1471082x15577017 · Cited by 134
“These techniques (Newman, 2004, 2006) often maximize the modularity score proposed by Girvan and Newman (2002) for clustering, using, for example, greedy heuristics (Blondel et al ., 2008).”
MethodNetwork modularity reveals critical scales for connectivity in ecology and evolution
Fletcher, R. J., Revell, A. Y., Reichert, B. E., Kitchens, W. M., Dixon, J., & Austin, J. D. (2013) · Nature Communications · doi:10.1038/ncomms3572 · Cited by 134
Analyzing big data in social media: Text and network analyses of an eating disorder forum
Moessner, M., Feldhege, J., Wolf, M., & Bauer, S. (2018) · International Journal of Eating Disorders · doi:10.1002/eat.22878 · Cited by 116
Defining a historic football team: Using Network Science to analyze Guardiola’s F.C. Barcelona
Buldú, J. M., Busquets, J., Echegoyen, I., & Seirul.lo, F. (2019) · Scientific Reports · doi:10.1038/s41598-019-49969-2 · Cited by 134
“mpute the minimal shortest-path p ij between all pairs of players using the Dijkstra’s algorithm61. Next, we define the average 13/17 shortest path d of the whole team as: d = 1 N(N 1) å i;j i6=j p ij (2) where N =11 is the total number of players of the team. Largest eigenvalue of the adjacency matrix The largest eige…”
MethodDescription-oriented community detection using exhaustive subgroup discovery
Atzmueller, M., Doerfel, S., & Mitzlaff, F. (2015) · Information Sciences · doi:10.1016/j.ins.2015.05.008 · Cited by 134
Social 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 - EDBT '08 · doi:10.1145/1352431.1352512 · Cited by 105
Estimating the number of communities by spectral methods
Le, C. M., & Levina, E. (2022) · Electronic Journal of Statistics · doi:10.1214/21-ejs1971 · Cited by 134
Large scale cohesive subgraphs discovery for social network visual analysis
Zhao, F., & Tung, A. K. H. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2535568.2448942 · Cited by 134
“Typical approach of community detection is to choose an objective function that captures a set of vertices with better internal connectivity than external connectivity, such as betweenness centrality [14] and modularity [20].”
BackgroundInternational Journal of Advanced Technology and Engineering Exploration
(2026) · International Journal of Advanced Technology and Engineering Exploration · doi:10.19101/ijatee · Cited by 134
Chen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M., & Zhang, Y. (2022) · Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3548606.3559352 · Cited by 133
“However, directly adopting classical community detection methods may lead to highly unbalanced shards in terms of shard size due to the specific structural properties of real-world graphs [20, 42, 64] (see Section 4.”
BackgroundDetecting local community structures in complex networks based on local degree central nodes
Chen, Q., Wu, T., & Fang, M. (2012) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2012.09.012 · Cited by 133
Exploring the GIS Knowledge Domain Using CiteSpace
Wei, F., Grubesic, T. H., & Bishop, B. W. (2015) · The Professional Geographer · doi:10.1080/00330124.2014.983588 · Cited by 133
“their connective capacity (Girvan and Newman, 2002).”
BackgroundA link clustering based overlapping community detection algorithm
Shi, C., Cai, Y., Fu, D., Dong, Y., & Wu, B. (2013) · Data & Knowledge Engineering · doi:10.1016/j.datak.2013.05.004 · Cited by 133
“A widely accepted criterion is the modularity Q proposed by Girvan–Newman [29], which quantitatively defines community structure as a node group that is densely intra-connected and sparsely inter-connected.”
BackgroundHalting in Random Walk Kernels
Sugiyama, M., & Borgwardt, K. M. (2015) · neural information processing systems · Cited by 133
Li, Z., Liu, J., & Wu, K. (2017) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2017.2720180 · Cited by 133
“These methods can be divided into four types: 1) hierarchical clustering [4], [6], [7]; 2) spectral methods [8]; 3) random walk-based methods [9]; and 4) genetic algorithm (GA)-based methods [10], [11].”
MethodBerahmand, K., Bouyer, A., & Vasighi, M. (2018) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2018.2879494 · Cited by 133
Sun, P. G., Gao, L., & Han, S. S. (2010) · Information Sciences · doi:10.1016/j.ins.2010.11.022 · Cited by 133
Rahman, S. A., & Schomburg, D. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl181 · Cited by 133
“A typical metabolic network consists of reactions, metabolites and enzymes, which can be modelled using graph theory ( Girvan and Newman, 2002; Jeong et al., 2000; Ma and Zeng, 2003; Oltvai and Barabasi, 2002; Schuster et al., 2000).”
BackgroundBalanced Multi-Label Propagation for Overlapping Community Detection in Social Networks
Wu, Z., Lin, Y., Gregory, S., Wan, H., & Tian, S. (2012) · Journal of Computer Science and Technology · doi:10.1007/s11390-012-1236-x · Cited by 132
“One of these is the well-known Girvan-Newman benchmark([16]), but this kind of synthetic network contains few important features of real-world networks.”
BackgroundResilience of networks with community structure behaves as if under an external field
Dong, G., Fan, J., Shekhtman, L., Shai, S., Du, R., Tian, L., Chen, X., Stanley, E., & Havlin, S. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801588115 · Cited by 132
Adaptive Graph Convolutional Network With Attention Graph Clustering for Co-Saliency Detection
Zhang, K., Li, T., Shen, S., Liu, B., Chen, J., & Liu, Q. (2020) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr42600.2020.00907 · Cited by 131
HiSCF: leveraging higher-order structures for clustering analysis in biological networks
Hu, L., Zhang, J., Pan, X., Yan, H., & You, Z. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa775 · Cited by 131
A community detection algorithm based on graph compression for large-scale social networks
Zhao, X., Liang, J., & Wang, J. (2020) · Information Sciences · doi:10.1016/j.ins.2020.10.057 · Cited by 131
Wang, Y., Di, Z., & Fan, Y. (2011) · PLoS ONE · doi:10.1371/annotation/1935b388-2831-4fb1-b8f2-914ab91c1ddc · Cited by 130
Bhargava, A., Arnold, A. P., Bangasser, D. A., Denton, K. M., Gupta, A., Hilliard Krause, L. M., Mayer, E. A., McCarthy, M., Miller, W. L., Raznahan, A., et al. (2021) · Endocrine Reviews · doi:10.1210/endrev/bnaa034 · Cited by 130
“In connectomes, the identification of subnetwork properties (165) can reveal how the complex functional and behavioral repertoire emerges from the simultaneous processes of segregated neuronal clusters and their D ow naded rom http/academ ic.”
BackgroundSHRINK: a structural clustering algorithm for detecting hierarchical communities in networks
Huang, J., Sun, H., Han, J., Deng, H., Sun, Y., & Liu, Y. (2010) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/1871437.1871469 · Cited by 130
Dynamic Bayesian Combination of Multiple Imperfect Classifiers
Simpson, E., Roberts, S., Psorakis, I., & Smith, A. M. (2013) · Studies in computational intelligence · doi:10.1007/978-3-642-36406-8_1 · Cited by 130
Zhang, T., Qiu, H., Castellano, G., Rifai, M., Chen, C. S., & Pianese, F. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3222417 · Cited by 75
Buehler, M. J. (2024) · Machine Learning: Science and Technology · doi:10.1088/2632-2153/ad7228 · Cited by 56
Mixing patterns and community structure in networksPreprint
Newman, M. E. J., & Girvan, M. (2013) · Cited by 130
Self-citationRefactoring android Java code for on-demand computation offloading
Zhang, Y., Huang, G., Liu, X., Zhang, W., Mei, H., & Yang, S. (2012) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2384616.2384634 · Cited by 129
“DPartner employs the Girvan and Newman [22] (shorten as G-N), a classical and often used clustering algorithm, to reveal the clusters in a graph.”
MethodThe Laplacian spectrum of neural networks
de Lange, S. C., de Reus, M. A., & van den Heuvel, M. P. (2014) · Frontiers in Computational Neuroscience · doi:10.3389/fncom.2013.00189 · Cited by 100
“The American football network described the games between Division IA colleges in 2000 and had 115 nodes and 613 undirected unweighted connections resulting in density 9.35% [http://www.cise.ufl.edu/research/sparse/matrices (Girvan and Newman, 2002)].”
BackgroundInfluentialCC-GA: A clustering coefficient based genetic algorithm for detecting communities in social networks
Said, A., Abbasi, R. A., Maqbool, O., Daud, A. Y., & Aljohani, N. R. (2017) · Applied Soft Computing · doi:10.1016/j.asoc.2017.11.014 · Cited by 129
Tulu, M. M., Hou, R., & Younas, T. (2018) · IEEE Access · doi:10.1109/access.2018.2794324 · Cited by 129
“American football network [21] is a network which has N = 115 teams or nodes, and the game between two teams represents the relation or edges between them.”
BackgroundMethodInfluentialGraph Neural Network Encoding for Community Detection in Attribute Networks
Sun, J., Zheng, W., Zhang, Q., & Xu, Z. (2022) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3051021 · Cited by 129
Chen, Y., Wang, S., Hilgetag, C. C., & Zhou, C. (2013) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002937 · Cited by 115
“A modular community is defined as a subnetwork with a higher density of connections relative to the entire network, based on the work by Newman [28].”
MethodCommunity structure in the United States House of Representatives
Porter, M. A., Mucha, P. J., Newman, M. E. J., & Friend, A. J. (2007) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2007.07.039 · Cited by 129
Self-citationRecent Progress on the Resilience of Complex Networks
Gao, J., Liu, X., Li, D., & Havlin, S. (2015) · Energies · doi:10.3390/en81012187 · Cited by 129
Sun, Y., Fan, H., Li, M., & Zipf, A. (2015) · Environment and Planning B Planning and Design · doi:10.1177/0265813515617642 · Cited by 128
Zhang, L., Pan, H., Su, Y., Zhang, X., & Niu, Y. (2017) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2017.2711038 · Cited by 128
Link Weight Prediction Using Supervised Learning Methods and Its Application to Yelp Layered Network
Fu, C., Zhao, M., Fan, L., Chen, X., Chen, J., Wu, Z., Xia, Y., & Xuan, Q. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2801854 · Cited by 128
“It is defined as where g st is the number of shortest paths between nodes s and t , and n ð i;j Þ st is the number of shortest paths between nodes s and t that pass through the edge ð i; j Þ [51].”
BackgroundMethodTopological and functional comparison of community detection algorithms in biological networks
Rahiminejad, S., Maurya, M. R., & Subramaniam, S. (2019) · BMC Bioinformatics · doi:10.1186/s12859-019-2746-0 · Cited by 129
Shishavan, S. T., & Gharehchopogh, F. S. (2022) · Multimedia Tools and Applications · doi:10.1007/s11042-022-12409-x · Cited by 128
Community-based anomaly detection in evolutionary networks
Chen, Z., Hendrix, W., & Samatova, N. F. (2011) · Journal of Intelligent Information Systems · doi:10.1007/s10844-011-0183-2 · Cited by 128
“Girvan and Newman (2002) has used this dataset as a static graph to detect the communities, while we construct the networks on a seasonal basis from spring to winter to discover community-based anomalies in the dynamic network.”
BackgroundMethodInfluentialCommunity Detection Algorithms in Healthcare Applications: A Systematic Review
Rostami, M., Oussalah, M., Berahmand, K., & Farrahi, V. (2023) · IEEE Access · doi:10.1109/access.2023.3260652 · Cited by 127
“Examples of divisive clustering methods include Girvan-Newman (GN) [79], edge clustering coefficient [80], and Information centrality [81].”
MethodA study of homophily on social media
Bişğin, H., Agarwal, N. K., & Xu, X. (2011) · World Wide Web · doi:10.1007/s11280-011-0143-3 · Cited by 129
“This has been the underlying phenomenon for the vast literature on community extraction [2, 13, 21, 23, 35].”
BackgroundDecay of interspecific avian flock networks along a disturbance gradient in Amazonia
Mokross, K. S., Ryder, T. B., Côrtes, M. C., Wolfe, J. D., & Stouffer, P. C. (2014) · Proceedings of the Royal Society B Biological Sciences · doi:10.1098/rspb.2013.2599 · Cited by 127
When are networks truly modular?
Reichardt, J., & Bornholdt, S. (2006) · Physica D: Nonlinear Phenomena · doi:10.1016/j.physd.2006.09.009 · Cited by 116
A Fast Algorithm for Streaming Betweenness Centrality
Green, O., McColl, R., & Bader, D. A. (2012) · International Conference on Social Computing · doi:10.1109/socialcom-passat.2012.37 · Cited by 126
“Brandes’s [5] algorithm for faster betweenness centrality is key for understanding the work that will be presented in the sections ahead.”
BackgroundDeciphering Network Community Structure by Surprise
Aldecoa, R., & Marín, I. (2011) · PLoS ONE · doi:10.1371/journal.pone.0024195 · Cited by 126
Towards Online Multiresolution Community Detection in Large-Scale Networks
Huang, J., Sun, H., Liu, Y., Song, Q., & Weninger, T. (2011) · PLoS ONE · doi:10.1371/journal.pone.0023829 · Cited by 126
Maji, G., Mandal, S., & Sen, S. (2020) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113681 · Cited by 126
Analysis of social voting patterns on digg
Lerman, K., & Galstyan, A. (2008) · doi:10.1145/1397735.1397738 · Cited by 126
“This latter phenomenon can be especially important in networks with well–defined community structure [6, 15].”
BackgroundParallel community detection on large networks with propinquity dynamics
Zhang, Y., Wang, J., Wang, Y., & Zhou, L. (2009) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1557019.1557127 · Cited by 126
Consistency of spectral hypergraph partitioning under planted partition model
Ghoshdastidar, D., & Dukkipati, A. (2017) · The Annals of Statistics · doi:10.1214/16-aos1453 · Cited by 125
Selected topics on applications of graph spectra
Cvetković, D., & Gutman, İ. (2011) · Cited by 125
Scale-free trees: The skeletons of complex networks
Kim, D., Noh, J. D., & Jeong, H. (2004) · Physical Review E · doi:10.1103/physreve.70.046126 · Cited by 125
Network isolation and local diversity in neutral metacommunities
Economo, E. P., & Keitt, T. H. (2010) · Oikos · doi:10.1111/j.1600-0706.2010.18272.x · Cited by 125
Supply Networks as Complex Systems: A Network-Science-Based Characterization
Brintrup, A. M., Wang, Y., & Tiwari, A. (2015) · IEEE Systems Journal · doi:10.1109/jsyst.2015.2425137 · Cited by 125
“Although different methods of calculation have been proposed, we use the popular method described by [20].”
MethodFortunato, S., & Castellano, C. (2009) · Springer eBooks · doi:10.1007/978-0-387-30440-3_76 · Cited by 125
“The most famous computer generated benchmark is a class of graphs designed by Girvan and Newman [14].”
BackgroundMethodInfluentialGarcía-Amado, L. R., Pérez, M. R., Iniesta-Arandia, I., Dahringer, G., Reyes, F., & Barrasa, S. (2012) · Ecology and Society · doi:10.5751/es-04855-170303 · Cited by 124
Using Mixed-Method Design and Network Analysis to Measure Development of Interagency Collaboration
Cross, J. E., Dickmann, E. M., Newman-Gonchar, R., & Fagan, J. M. (2009) · American Journal of Evaluation · doi:10.1177/1098214009340044 · Cited by 124
“…limited in their ability to identify the communities of actors which best characterize the social divisions in a particular graph and can exclude peripheral actors from communities to which they would logically belong (Fortunato & Castellano, 2007; Girvan & Newman, 2002; Wasserman & Faust, 1994).”
BackgroundSocial Network Analysis in the Study of Terrorism and Insurgency: From Organization to Politics
Zech, S. T., & Gabbay, M. (2016) · International Studies Review · doi:10.1093/isr/viv011 · Cited by 124
“Algorithms for detecting community structure use the pattern of ties between nodes to assign them to distinct clusters (Girvan and Newman 2002).”
BackgroundBaldassano, S. N., & Bassett, D. S. (2016) · Scientific Reports · doi:10.1038/srep26087 · Cited by 112
Susarla, A., Oh, J.-H., & Tan, Y. (2016) · Journal of Management Information Systems · doi:10.1080/07421222.2016.1172454 · Cited by 100
“3 Clustering denotes that if two nodes are neighbors of the same third node, there is a greater probability of the two nodes also sharing a tie [30], indicating a high ratio of ties from within groups to ties between groups.”
BackgroundMetastability and chimera states in modular delay and pulse-coupled oscillator networks
Wildie, M., & Shanahan, M. (2012) · Chaos: An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.4766592 · Cited by 115
Parallel SimRank computation on large graphs with iterative aggregation
He, G., Feng, H., Li, C., & Chen, H. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835874 · Cited by 124
“There is a lot of research work on static graph analysis, including power laws discovery [30], frequent pattern mining [40, 39], clustering and community identification [32, 13], and node ranking [33, 18].”
BackgroundA complex network approach towards modeling and analysis of the Australian Airport Network
Hossain, M. M., & Alam, S. (2016) · Journal of Air Transport Management · doi:10.1016/j.jairtraman.2016.12.008 · Cited by 124
Systems Biology in the Context of Big Data and Networks
Altaf-Ul-Amin, M., Afendi, F. M., Kiboi, S. K., & Kanaya, S. (2014) · BioMed Research International · doi:10.1155/2014/428570 · Cited by 123
“There are versatile graph clustering methods such as based on density and periphery [69], random walk [70], betweenness centrality [71], and so on.”
MethodCommunity-Enhanced De-anonymization of Online Social Networks
Nilizadeh, S., Kapadia, A. C., & Ahn, Y. (2014) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2660267.2660324 · Cited by 123
Link prediction via matrix completion
Pech, R., Hao, D., Pan, L., Cheng, H., & Zhou, T. (2017) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/117/38002 · Cited by 123
Graph regularized nonnegative matrix factorization for temporal link prediction in dynamic networks
Ma, X., Sun, P., & Wang, Y. (2017) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2017.12.092 · Cited by 123
A network-based ranking system for US college football
Park, J. M., & Newman, M. E. J. (2005) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2005/10/p10014 · Cited by 123
“The schedule of games for a season can be represented as a network or graph in which the vertices represent colleges and there is an edge between two colleges if they played a regular season game during the season of interest [5].”
BackgroundSelf-citationCommunity structure and ethnic preferences in school friendship networks
González, M. C., Herrmann, H. J., Kertész, J., & Vicsek, T. (2007) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2007.01.002 · Cited by 123
Information resonance on Twitter: watching Iran
Zhou, Z., Bandari, R., Kong, J. S., Qian, H., & Roychowdhury, V. (2010) · doi:10.1145/1964858.1964875 · Cited by 122
“Research work conducted on modeling and analyzing various aspects of social networks have identified many recurring patterns, such as power law degree distributions, small world, local clustering and communities structures [4, 9, 12, 19, 20], in the underlying friendship or contact networks.”
BackgroundInfluence Maximization on Large-Scale Mobile Social Network: A Divide-and-Conquer Method
Song, G., Zhou, X., Wang, Y., & Xie, K. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2014.2320515 · Cited by 122
“Index Terms—Mobile social network, influence maximization, greedy algorithm, divide-and-conquer Ç”
BackgroundEnhancing community detection using a network weighting strategy
Meo, P. D., Ferrara, E., Fiumara, G., & Provetti, A. (2012) · Information Sciences · doi:10.1016/j.ins.2012.08.001 · Cited by 122
“Consider, for instance, the first (and one of the most popular) algorithm to maximize modularity: the Girvan-Newman algorithm [23, 42].”
BackgroundMethodA Monte Carlo evaluation of weighted community detection algorithms
Gates, K. M., Henry, T., Steinley, D., & Fair, D. A. (2016) · Frontiers in Neuroinformatics · doi:10.3389/fninf.2016.00045 · Cited by 106
“The first index is the commonly used Girvan and Newman (2002)’s approach of looking at the fraction of correctly classified nodes.”
MethodLoneliness and meaning in life are reflected in the intrinsic network architecture of the brain
Mwilambwe-Tshilobo, L., Ge, T., Chong, M., Ferguson, M. A., Misic, B., Burrow, A. L., Leahy, R. M., & Spreng, R. N. (2019) · Social Cognitive and Affective Neuroscience · doi:10.1093/scan/nsz021 · Cited by 116
“To further characterize the pattern of connectivity identified by the PLS analysis, we quantified modularity, a global network measure that estimates how well a network can be divided into modules (or communities) with stronger within-module than between-module connections (Girvan and Newman, 2002).”
MethodThe brain's connective core and its role in animal cognition
Shanahan, M. (2012) · Philosophical Transactions of the Royal Society B: Biological Sciences · doi:10.1098/rstb.2012.0128 · Cited by 115
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.