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 201–300 of 1,049
Rings in Clinical Trials and Drugs: Present and Future
Shearer, J., Castro, J. L., Lawson, A. D. G., MacCoss, M., & Taylor, R. D. (2022) · Journal of Medicinal Chemistry · doi:10.1021/acs.jmedchem.2c00473 · Cited by 479
Percolation transition in dynamical traffic network with evolving critical bottlenecks
Li, D., Fu, B., Wang, Y., Lu, G., Berezin, Y., Stanley, H. E., & Havlin, S. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1419185112 · Cited by 475
Community Discovery in Dynamic Networks: A Survey
Rossetti, G., & Cazabet, R. (2019) · ACM Computing Surveys · doi:10.1145/3172867 · Cited by 468
“Complex Networks (Newman, 2003) are popular tools – both theoretical and analytical – commonly used to describe and analyze interaction phenomena that occur in the real world: social ties, economic transaction, communication, human mobility are a few examples of observable phenomena that are often investigated using i…”
InfluentialInformetrics at the beginning of the 21st century—A review
Bar-Ilan, J. (2008) · Journal of Informetrics · doi:10.1016/j.joi.2007.11.001 · Cited by 466
Understanding brain networks and brain organization
Pessoa, L. (2014) · Physics of Life Reviews · doi:10.1016/j.plrev.2014.03.005 · Cited by 464
“Communities are determined by subdividing a network into groups of nodes, often by maximizing the number of within-group links, and minimizing the number of between-group links [142].”
BackgroundStatistical Mechanics: Entropy, Order Parameters, and Complexity
Sethna, J. P. (2021) · doi:10.1093/oso/9780198865247.001.0001 · Cited by 464
Eom, K., Park, H. S., Yoon, D. S., & Kwon, T. (2011) · Physics Reports · doi:10.1016/j.physrep.2011.03.002 · Cited by 464
Sustaining the Internet with hyperbolic mapping
Boguñá, M., Papadopoulos, F., & Krioukov, D. (2010) · Nature Communications · doi:10.1038/ncomms1063 · Cited by 463
“These observations build our confidence that our mapping method provides meaningful results reflecting peculiarities of the real Internet structure, and suggest that the method can be adapted to discover the community structur”
MethodBernhardt, B. C., Chen, Z., He, Y., Evans, A. C., & Bernasconi, N. (2011) · Cerebral Cortex · doi:10.1093/cercor/bhq291 · Cited by 463
Crona, B., & Bodin, Ö. (2006) · Ecology and Society · doi:10.5751/es-01793-110207 · Cited by 459
Novák, P., Neumann, P., & Macas, J. (2010) · BMC Bioinformatics · doi:10.1186/1471-2105-11-378 · Cited by 458
“To deal with this problem, we performed further analysis of the graph structure using a hierarchical agglomeration algorithm [13] for detecting communities [14] which are defined as groups of vertices in a graph that are more densely connected internally than with the rest of the graph (Fig.”
MethodHINT: High-quality protein interactomes and their applications in understanding human disease
Das, J., & Yu, H. (2012) · BMC Systems Biology · doi:10.1186/1752-0509-6-92 · Cited by 458
“We calculated the clustering coefficient [37] and the edge betweenness [38] for the different interaction networks in HINT.”
MethodFinding communities in linear time: a physics approach
Wu, F., & Huberman, B. A. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00125-x · Cited by 451
“We test our algorithm against the US college football data studied by Girvan and Newman [3].”
BackgroundMethodInfluentialThe ground truth about metadata and community detection in networks
Peel, L., Larremore, D. B., & Clauset, A. (2017) · Science Advances · doi:10.1126/sciadv.1602548 · Cited by 449
The Internet of Things (IoT) in healthcare: Taking stock and moving forward
Rejeb, A., Rejeb, K., Treiblmaier, H., Appolloni, A., Alghamdi, S., Alhasawi, Y., & Iranmanesh, M. (2023) · Internet of Things · doi:10.1016/j.iot.2023.100721 · Cited by 448
Analysis of the structure of complex networks at different resolution levels
Arenas, A., Fernández, A., & Gómez, S. (2008) · New Journal of Physics · doi:10.1088/1367-2630/10/5/053039 · Cited by 446
“The problem is that the R&B method consisting into varying γ (the prefactor that multiplies the null model) is not equivalent to tune the resolution of Newman’s modularity.”
BackgroundInfluentialCommunity discovery using nonnegative matrix factorization
Wang, F., Li, T., Wang, X., Zhu, S., & Ding, C. (2011) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0181-y · Cited by 446
“2005), which are usually called clusters or communities (Girvan and Newman 2002).”
BackgroundData-intensive text processing with MapReduce
Lin, J., & Dyer, C. (2009) · Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Tutorial Abstracts on - NAACL '09 · doi:10.3115/1620950.1620951 · Cited by 445
A framework for community identification in dynamic social networks
Tantipathananandh, C., Berger-Wolf, T., & Kempe, D. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281269 · Cited by 443
“One of the most important questions in social networks is the identification of “communities”, which are loosely defined as collections of individuals who interact unusually frequently [12, 13, 16, 18, 27, 38].”
BackgroundGeneralized Louvain method for community detection in large networks
De Meo, P., Ferrara, E., Fiumara, G., & Provetti, A. (2011) · 2011 11th International Conference on Intelligent Systems Design and Applications · doi:10.1109/isda.2011.6121636 · Cited by 440
“Our analysis puts into evidence the following observations: i) classic not optimized algorithms (for example Girvan-Newman [8]) are unfeasible for large network analysis; ii) results obtained by using LM are slightly higher than those obtained by using FKCD; on the other hand, LM adopts local information in order to o…”
BackgroundMethodInfluentialStatistical properties of sampled networks
Lee, S. H., Kim, P.-J., & Jeong, H. (2006) · Physical Review E · doi:10.1103/physreve.73.016102 · Cited by 440
Detecting functional modules in the yeast protein–protein interaction network
Chen, J., & Yuan, B. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl370 · Cited by 440
“By removing these linkers stepby-step, one would eventually obtain the community structure of a graph as a hierarchical tree (Girvan and Newman, 2002).”
InfluentialStatistical physics of inference: thresholds and algorithms
Zdeborová, L., & Krzakala, F. (2016) · Advances in Physics · doi:10.1080/00018732.2016.1211393 · Cited by 440
“An influential set of works on community detection is due to Mark Newman and collaborators who introduced the so-called modularity function [51, 86, 182]”
BackgroundControllability of complex networks via pinning
Sorrentino, F., di Bernardo, M., Garofalo, F., & Chen, G. (2007) · Physical Review E · doi:10.1103/physreve.75.046103 · Cited by 439
Community detection in networks with positive and negative links
Traag, V. A., & Bruggeman, J. (2009) · Physical Review E · doi:10.1103/physreve.80.036115 · Cited by 434
“fm which quantifies the discrepancy between communities in actual networks and in their random counterparts [9].”
BackgroundA scientometric review of global BIM research: Analysis and visualization
Zhao, X. (2017) · Automation in Construction · doi:10.1016/j.autcon.2017.04.002 · Cited by 434
A wellness study of 108 individuals using personal, dense, dynamic data clouds
Price, N. D., Magis, A. T., Earls, J. C., Glusman, G., Levy, R., Lausted, C., McDonald, D. T., Kusebauch, U., Moss, C. L., Zhou, Y., et al. (2017) · Nature Biotechnology · doi:10.1038/nbt.3870 · Cited by 427
Towards an explanatory and computational theory of scientific discovery
Chen, C., Chen, Y., Horowitz, M., Hou, H., Liu, Z., & Pellegrino, D. (2009) · Journal of Informetrics · doi:10.1016/j.joi.2009.03.004 · Cited by 426
“Co-author networks have also been studied in complex network analysis of community structures (Girvan & Newman, 2002).”
Email as Spectroscopy: Automated Discovery of Community Structure within Organizations
Tyler, J. R., Wilkinson, D. M., & Huberman, B. A. (2003) · Communities and Technologies · doi:10.1007/978-94-017-0115-0_5 · Cited by 425
Classes of complex networks defined by role-to-role connectivity profiles
Guimerà, R., Sales-Pardo, M., & Amaral, L. A. N. (2007) · Nature Physics · doi:10.1038/nphys489 · Cited by 425
“two strict conditions is fulfilled: (i) the network lacks a modular structure 9,10,11,12,13,14 , or (ii) the network has a modular structure but (ii.a) all modules were formed according to the same mechanisms, and therefore have similar properties, and (ii.b) the interface between modules is…”
BackgroundSpectral methods for community detection and graph partitioning
Newman, M. E. J. (2013) · Physical Review E · doi:10.1103/physreve.88.042822 · Cited by 424
“Figure 2 shows results from the application of the method to networks generated using the stochastic block model of Section III, which in addition to its use in community inference is also widely used as a benchmark test for community detection methods [27, 33].”
Self-citationFunctional topology in a network of protein interactions
Pržulj, N., Wigle, D. A., & Jurisica, I. (2004) · Bioinformatics · doi:10.1093/bioinformatics/btg415 · Cited by 422
Fuzzy communities and the concept of bridgeness in complex networks
Nepusz, T., Petróczi, A., Négyessy, L., & Bazsó, F. (2008) · Physical Review E · doi:10.1103/physreve.77.016107 · Cited by 421
Understanding Tissue-Specific Gene Regulation
Sonawane, A. R., Platig, J., Fagny, M., Chen, C.-Y., Paulson, J. N., Lopes-Ramos, C. M., DeMeo, D. L., Quackenbush, J., Glass, K., & Kuijjer, M. L. (2017) · Cell Reports · doi:10.1016/j.celrep.2017.10.001 · Cited by 421
MGAE: Marginalized Graph Autoencoder for Graph Clustering
Wang, C., Pan, S., Long, G., Zhu, X., & Jiang, J. (2017) · Proceedings of the 2017 ACM on Conference on Information and Knowledge Management · doi:10.1145/3132847.3132967 · Cited by 420
“Girvan et al. proposed a method for detecting social communities through the idea of using centrality indices to find community boundaries [7]; Hasting et al. expressed community detection as an inference problem to determine the most likely arrangement of communities and applied belief propagation…”
BackgroundMethodSocial network analysis: An overview
Tabassum, S., Pereira, F. S. F., Fernandes, S., & Gama, J. (2018) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1256 · Cited by 419
“This is usually done by iteratively removing the bridges between groups of vertices, as suggested by Girvan and Newman (2002).”
MethodInfluentialDefining and identifying Sleeping Beauties in science
Ke, Q., Ferrara, E., Radicchi, F., & Flammini, A. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1424329112 · Cited by 416
“This paper was essentially unnoticed for about 30 y, but then became suddenly important in network science research after the publication of the seminal paper by Girvan and Newman, which adopts the social network described in the Zachary paper as a paradigmatic benchmark to validate community detection methods on grap…”
BackgroundRelationships and the social brain: Integrating psychological and evolutionary perspectives
Sutcliffe, A., Dunbar, R., Binder, J., & Arrow, H. (2012) · British Journal of Psychology · doi:10.1111/j.2044-8295.2011.02061.x · Cited by 415
“Although close friends of a given individual are more likely to be friends (a property known as clustering or network transitivity), the probability that any two of my friends are also friends with each other tends to fall between 10% and 50% (Girvan & Newman, 2002).”
BackgroundGlobal diversity of microbial communities in marine sediment
Hoshino, T., Doi, H., Uramoto, G.-I., Wörmer, L., Adhikari, R. R., Xiao, N., Morono, Y., D’Hondt, S., Hinrichs, K.-U., & Inagaki, F. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1919139117 · Cited by 412
“Fifty communities were detected, based on edge-betweenness clustering (53).”
BackgroundIntegrating protein structural dynamics and evolutionary analysis with Bio3D
Skjærven, L., Yao, X.-Q., Scarabelli, G., & Grant, B. J. (2014) · BMC Bioinformatics · doi:10.1186/s12859-014-0399-6 · Cited by 411
“Girvan and Newman betweeness clustering [39] is then performed to generate aggregate nodal clusters, or communities, that are highly intraconnected but loosely inter-connected.”
BackgroundWang, Q., Sporns, O., & Burkhalter, A. (2012) · The Journal of Neuroscience · doi:10.1523/jneurosci.6063-11.2012 · Cited by 410
“We computed the modularity and the optimal modularity partition of M using a modularity metric that is based on the density of connections within modules relative to the density between modules (Girvan and Newman, 2002).”
MethodThe science of science: From the perspective of complex systems
Zeng, A., Shen, Z., Zhou, J., Wu, J., Fan, Y., Wang, Y., & Stanley, H. E. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.10.001 · Cited by 410
“Collaboration networks are also found to have community structure [50].”
BackgroundRevealing travel patterns and city structure with taxi trip data
Liu, X., Gong, L., Gong, Y., & Liu, Y. (2015) · Journal of Transport Geography · doi:10.1016/j.jtrangeo.2015.01.016 · Cited by 408
“We use actual trajectory distance instead of Euclidean distance between origin and destination as the length of the trip, because traveling by taxi cost more than other means of transportation so that people are sensitive to the price of the trip, which correlate with the actual trajectory distance.”
MethodModule identification in bipartite and directed networks
Guimerà, R., Sales-Pardo, M., & Amaral, L. A. N. (2007) · Physical Review E · doi:10.1103/physreve.76.036102 · Cited by 406
Multi-level governance and power in climate change policy networks
Di Gregorio, M., Fatorelli, L., Paavola, J., Locatelli, B., Pramova, E., Nurrochmat, D. R., May, P. H., Brockhaus, M., Sari, I. M., & Kusumadewi, S. D. (2019) · Global Environmental Change · doi:10.1016/j.gloenvcha.2018.10.003 · Cited by 406
Evolutionary Large-Scale Multi-Objective Optimization: A Survey
Tian, Y., Si, L., Zhang, X., Cheng, R., He, C., Tan, K. C., & Jin, Y. (2022) · ACM Computing Surveys · doi:10.1145/3470971 · Cited by 401
“Many real-world complex systems can be represented by networks, in which the nodes denote the objects (e.g. individuals in social networks [52] and genes in biological networks [103]) and the edges denote the connections between objects.”
BackgroundAssessing experimentally derived interactions in a small world
Goldberg, D. S., & Roth, F. P. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0735871100 · Cited by 400
Overlapping community detection using Bayesian non-negative matrix factorization
Psorakis, I., Roberts, S., Ebden, M., & Sheldon, B. (2011) · Physical Review E · doi:10.1103/physreve.83.066114 · Cited by 399
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
Lambiotte, R., Delvenne, J.-C., & Barahona, M. (2014) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2015.2391998 · Cited by 398
“GS π is a measure of entropy of the partition according to the values of π , i.e., the degree.”
BackgroundGraph theory and networks in Biology
Mason, O., & Verwoerd, M. (2007) · IET Systems Biology · doi:10.1049/iet-syb:20060038 · Cited by 398
“In [68, 137, 150, 61] the notions of betweenness and information centrality were first extended to apply to edges rather than nodes.”
BackgroundGallos, L. K., Makse, H. A., & Sigman, M. (2012) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1106612109 · Cited by 398
A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning
Jin, D., Yu, Z., Jiao, P., Pan, S., He, D., Wu, J., Yu, P., & Zhang, W. (2021) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3104155 · Cited by 397
Core-Periphery Structure in NetworksPreprint
Puck, M., Mason, R., Porter, A., Fowler, J. H., & Mucha, P. J. (2013) · Cited by 397
Universality in network dynamics
Barzel, B., & Barabási, A.-L. (2013) · Nature Physics · doi:10.1038/nphys2741 · Cited by 396
“…of networks observed in nature and technology, their topology shares several highly reproducible and often universal characteristics [1–8]: many real networks display the small world property [9], are scale-free [10], develop distinct community structure [11], and show degree correlations [12, 13].”
A measure of centrality based on network efficiency
Latora, V, & Marchiori, M. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/188 · Cited by 396
Memory in network flows and its effects on spreading dynamics and community detection
Rosvall, M., Esquivel, A. V., Lancichinetti, A., West, J. D., & Lambiotte, R. (2014) · Nature Communications · doi:10.1038/ncomms5630 · Cited by 395
Gong, M., Cai, Q., Chen, X., & Ma, L. (2014) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2013.2260862 · Cited by 394
“CNM was proposed by Clauset, Newman, and Moore [60].”
BackgroundInfluentialRosvall, M., & Bergstrom, C. T. (2011) · PLoS ONE · doi:10.1371/journal.pone.0018209 · Cited by 393
“(4) At each submodule level, q is the rate of codeword use for entering the mi submodules or exiting to a coarser level and H(Q) is the frequency-weighted average length of the codewords in the subindex codebook.”
BackgroundUncovering Patterns of Inter-Urban Trip and Spatial Interaction from Social Media Check-In Data
Liu, Y., Sui, Z., Kang, C., & Gao, Y. (2014) · PLoS ONE · doi:10.1371/journal.pone.0086026 · Cited by 393
“Many algorithms have been proposed for detecting communities, including the GirvanNewman method [45], multilevel method [46], fastgreedy method [47], infomap method [48], walktrap method [49], and others.”
MethodPark, J., Wood, I. B., Jing, E., Nematzadeh, A., Ghosh, S., Conover, M. D., & Ahn, Y.-Y. (2019) · Nature Communications · doi:10.1038/s41467-019-11380-w · Cited by 393
Control Profiles of Complex Networks
Ruths, J., & Ruths, D. (2014) · Science · doi:10.1126/science.1242063 · Cited by 391
A cellular and spatial map of the choroid plexus across brain ventricles and ages
Dani, N., Herbst, R. H., McCabe, C., Green, G. S., Kaiser, K., Head, J. P., Cui, J., Shipley, F. B., Jang, A., Dionne, D., et al. (2021) · Cell · doi:10.1016/j.cell.2021.04.003 · Cited by 388
Ghiassian, S. D., Menche, J., & Barabási, A.-L. (2015) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004120 · Cited by 388
Vulnerability and protection of infrastructure networks
Latora, V., & Marchiori, M. (2005) · Physical Review E · doi:10.1103/physreve.71.015103 · Cited by 387
Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data
Narang, S. K., & Ortega, A. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2188718 · Cited by 387
Efficient and principled method for detecting communities in networks
Ball, B., Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.84.036103 · Cited by 386
Self-citationRandom walk with restart: fast solutions and applications
Tong, H., Faloutsos, C., & Pan, J.-Y. (2008) · Knowledge and Information Systems · doi:10.1007/s10115-007-0094-2 · Cited by 384
Community Mining from Signed Social Networks
Yang, B., Cheung, W., & Liu, J. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.1061 · Cited by 383
“…on the structural similarity metrics [18], [19], [20] and divisive methods based on betweenness metrics, like the Girvan-Newman (GN) algorithm [5], the Tyler algorithm [21], and the Radicchi algorithm [22], and 3) methods for detecting hyperlink-based Web communities such as the maximum flow…”
BackgroundMethodInfluentialQuantitative function for community detection
Li, Z., Zhang, S., Wang, R.-S., Zhang, X.-S., & Chen, L. (2008) · Physical Review E · doi:10.1103/physreve.77.036109 · Cited by 382
Detecting network communities: a new systematic and efficient algorithm
Donetti, L., & Muñoz, M. A. (2004) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2004/10/p10012 · Cited by 374
Toward a formalized account of attitudes: The Causal Attitude Network (CAN) model.
Dalege, J., Borsboom, D., van Harreveld, F., van den Berg, H., Conner, M., & van der Maas, H. L. J. (2016) · Psychological Review · doi:10.1037/a0039802 · Cited by 373
Approaches for Extracting Practical Information from Gene Co-expression Networks in Plant Biology
Aoki, K., Ogata, Y., & Shibata, D. (2007) · Plant and Cell Physiology · doi:10.1093/pcp/pcm013 · Cited by 372
Complex Networks: Principles, Methods and Applications
Latora, V., Nicosia, V., & Russo, G. (2017) · Cambridge University Press eBooks · doi:10.1017/9781316216002 · Cited by 372
Revealing the dynamic network structure of the Beck Depression Inventory-II
Bringmann, L. F., Lemmens, L. H. J. M., Huibers, M. J. H., Borsboom, D., & Tuerlinckx, F. (2015) · Psychological Medicine · doi:10.1017/s0033291714001809 · Cited by 371
“Revealing the dynamic network structure of the”
BackgroundA tutorial in connectome analysis: Topological and spatial features of brain networks
Kaiser, M. (2011) · NeuroImage · doi:10.1016/j.neuroimage.2011.05.025 · Cited by 371
Subnetwork hierarchies of biochemical pathways
Holme, P., Huss, M., & Jeong, H. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg033 · Cited by 367
“The algorithm—a development of the algorithms by Girvan and Newman (2002), and Schuster et al.”
BackgroundMethodInfluentialBaggio, R., Scott, N., & Cooper, C. (2010) · Annals of Tourism Research · doi:10.1016/j.annals.2010.02.008 · Cited by 366
Detection of topological patterns in complex networks: correlation profile of the internet
Maslov, S., Sneppen, K., & Zaliznyak, A. (2004) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2003.06.002 · Cited by 364
Comprehensive survey on hierarchical clustering algorithms and the recent developments
Ran, X., Xi, Y., Lu, Y., Wang, X., & Lu, Z. (2023) · Artificial Intelligence Review · doi:10.1007/s10462-022-10366-3 · Cited by 361
Demonstrating microbial co-occurrence pattern analyses within and between ecosystems
Williams, R. J., Howe, A., & Hofmockel, K. S. (2014) · Frontiers in Microbiology · doi:10.3389/fmicb.2014.00358 · Cited by 361
Social Network Analysis and Mining for Business Applications
Bonchi, F., Castillo, C., Gionis, A., & Jaimes, A. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961194 · Cited by 359
“…small diameter (i.e., the maximum possible distance between two nodes measured as length of the shortest path), exhibit smallworld structure [Watts and Strogatz 1998], and community structure [Girvan and Newman 2002], are only few of the ubiquitous properties that many researchers have veri.ed.”
BackgroundMethodSegregated Systems of Human Brain Networks
Wig, G. S. (2017) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2017.09.006 · Cited by 357
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication
Leskovec, J., Chakrabarti, D., Kleinberg, J., & Faloutsos, C. (2005) · Lecture Notes in Computer Science · doi:10.1007/11564126_17 · Cited by 356
Blockade of TNF-α rapidly inhibits pain responses in the central nervous system
Hess, A., Axmann, R., Rech, J., Finzel, S., Heindl, C., Kreitz, S., Sergeeva, M., Saake, M., Garcia, M., Kollias, G., et al. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1011774108 · Cited by 356
Detecting network communities by propagating labels under constraints
Barber, M. J., & Clark, J. W. (2009) · Physical Review E · doi:10.1103/physreve.80.026129 · Cited by 355
Kim, J., Calhoun, V. D., Shim, E., & Lee, J.-H. (2016) · NeuroImage · doi:10.1016/j.neuroimage.2015.05.018 · Cited by 354
“The modularity of the learned features in each hidden layer was further analyzed via a graph-theoretical measurement (Girvan and Newman, 2002; Newman and Girvan, 2004) implemented in a graphtheoretical analysis toolbox (Hosseini et al., 2012 ).”
A classification for community discovery methods in complex networks
Coscia, M., Giannotti, F., & Pedreschi, D. (2011) · Statistical Analysis and Data Mining: The ASA Data Science Journal · doi:10.1002/sam.10133 · Cited by 353
A Comprehensive Survey on Community Detection With Deep Learning
Su, X., Xue, S., Liu, F., Wu, J., Yang, J., Zhou, C., Hu, W., Paris, C., Nepal, S., Jin, D., et al. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3137396 · Cited by 353
“Girvan and New-man [3] opened up a new direction in community detection through graph partitioning.”
BackgroundMethodInfluentialRobustness of community structure in networks
Karrer, B., Levina, E., & Newman, M. E. J. (2008) · Physical Review E · doi:10.1103/physreve.77.046119 · Cited by 350
“A large number of methods for finding communities have been proposed in recent years, including divisive methods based on betweenness and similar measures [8, 9], methods based on searching for small cliques [10, 11], information-theoretic techniques [12], statistical inference through belief propagation [13] or maxim…”
MethodSelf-citationUncovering space-independent communities in spatial networks
Expert, P., Evans, T. S., Blondel, V. D., & Lambiotte, R. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1018962108 · Cited by 350
Geographic Constraints on Social Network Groups
Onnela, J.-P., Arbesman, S., González, M. C., Barabási, A.-L., & Christakis, N. A. (2011) · PLoS ONE · doi:10.1371/journal.pone.0016939 · Cited by 349
The Network Structure of Food Webs
Dunne, J. A. (2005) · Ecological Networks · doi:10.1093/oso/9780195188165.003.0002 · Cited by 348
Genomic analysis of the hierarchical structure of regulatory networks
Yu, H., & Gerstein, M. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0508637103 · Cited by 348
A Multiobjective Genetic Algorithm to Find Communities in Complex Networks
Pizzuti, C. (2012) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2011.2161090 · Cited by 346
“A reference approach to multiobjective clustering algorithms for numerical and categorical data is that proposed by Handl and Knowles [28], and named multiobjective clustering with automatic K-determination (MOCK).”
BackgroundMethodCommunity detection in social networks
Bedi, P., & Sharma, C. (2016) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1178 · Cited by 346
Entangled Networks, Synchronization, and Optimal Network Topology
Donetti, L., Hurtado, P. I., & Muñoz, M. A. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.188701 · Cited by 346
Laplacian Dynamics and Multiscale Modular Structure in Networks
Lambiotte, R., Delvenne, J., & Barahona, M. (2008) · doi:10.48550/arxiv.0812.1770 · Cited by 345
Analysis of a large-scale weighted network of one-to-one human communication
Onnela, J.-P., Saramäki, J., Hyvönen, J., Szabó, G., Menezes, M. A. D., Kaski, K., Barabási, A.-L., & Kertész, J. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/179 · Cited by 344
The implications of network structure for epidemic dynamics
Keeling, M. (2005) · Theoretical Population Biology · doi:10.1016/j.tpb.2004.08.002 · Cited by 342
FENNEL: streaming graph partitioning for massive scale graphs
Tsourakakis, C., Gkantsidis, C., Radunovic, B., & Vojnovic, M. (2014) · Proceedings of the 7th ACM international conference on Web search and data mining · doi:10.1145/2556195.2556213 · Cited by 341
“This is intimately related to the concepts of graph modularity [11] and quasi-cliques [30].”
Background
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.