The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Fast algorithm for detecting community structure in networks
Open accessAbstract
Many networks display community structure--groups of vertices within which connections are dense but between which they are sparser--and sensitive computer algorithms have in recent years been developed for detecting this structure. These algorithms, however, are computationally demanding, which limits their application to small networks. Here we describe an algorithm which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms. We give several example applications, including one to a collaboration network of more than 50,000 physicists.
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.
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
Statistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Self-citationCommunity structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502 · cited 5×
“601 for the best split reported in [5].”
BackgroundMethodInfluentialSelf-citationFinding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931 · cited 5×
“Girvan and Newman [5, 6] proposed a computer algorithm based on the iterative removal of edges with high “betweenness” scores that appears to identify such structure with some sensitivity, and this algorithm has been employed by a number of authors in the study of such diverse systems as networks…”
BackgroundMethodInfluentialSelf-citationEveritt, B. J., Landau, S., & Leese, M. (1974) · Cited by 9,358
Strogatz, S. H. (2001) · Nature · doi:10.1038/35065725 · Cited by 8,302
Social Network Analysis: A Handbook.
Pappi, F. U., & Scott, J. (1993) · Contemporary Sociology · doi:10.2307/2075047 · Cited by 5,969
An Information Flow Model for Conflict and Fission in Small Groups
Zachary, W. W. (1977) · Journal of Anthropological Research · doi:10.1086/jar.33.4.3629752 · Cited by 4,704
The structure of scientific collaboration networks
Newman, M. E. J. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.98.2.404 · Cited by 4,482
Self-citationDorogovtsev, S. N., & Mendes, J. F. F. (2003) · doi:10.1093/acprof:oso/9780198515906.001.0001 · Cited by 1,563
Research works printed but not linked: 1
- 10.1103/RevModPhys.74.47 · DOI · Paper page
Cited by
Items 101–183 of 183
Ghiassian, S. D., Menche, J., & Barabási, A.-L. (2015) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004120 · Cited by 388
Task-Based Core-Periphery Organization of Human Brain Dynamics
Bassett, D. S., Wymbs, N. F., Rombach, M. P., Porter, M. A., Mucha, P. J., & Grafton, S. T. (2013) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003171 · Cited by 356
“thought to play an important role in information processing in the human brain [1]. At the small scale of individual neurons, temporally coherent activity supports information transfer between cells [2]. At a much larger scale, simultaneously active cortical areas form functional systems that enable behavior [1]. Howe…”
BackgroundMethodCommunity 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
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
Complex Networks: Principles, Methods and Applications
Latora, V., Nicosia, V., & Russo, G. (2017) · Cambridge University Press eBooks · doi:10.1017/9781316216002 · Cited by 372
A 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
Principles and methods of integrative genomic analyses in cancer
Kristensen, V. N., Lingjærde, O. C., Russnes, H. G., Vollan, H. K. M., Frigessi, A., & Børresen-Dale, A.-L. (2014) · Nature Reviews Cancer · doi:10.1038/nrc3721 · Cited by 371
Distributed community detection in delay tolerant networks
Hui, P., Yoneki, E., Chan, S. Y., & Crowcroft, J. (2007) · Proceedings of 2nd ACM/IEEE international workshop on Mobility in the evolving internet architecture · doi:10.1145/1366919.1366929 · Cited by 370
Discovering social circles in ego networks
Mcauley, J., & Leskovec, J. (2014) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2556612 · Cited by 366
Combining link and content for community detection: a discriminative approach
Yang, T., Jin, R., Chi, Y., & Zhu, S. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557120 · Cited by 364
Simple models of human brain functional networks
Vértes, P. E., Alexander-Bloch, A. F., Gogtay, N., Giedd, J. N., Rapoport, J. L., & Bullmore, E. T. (2012) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1111738109 · Cited by 357
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
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
The physics of communicability in complex networks
Estrada, E., Hatano, N., & Benzi, M. (2012) · Physics Reports · doi:10.1016/j.physrep.2012.01.006 · Cited by 352
Unsupervised Pattern Discovery in Speech
Park, A. S., & Glass, J. R. (2008) · IEEE Transactions on Audio, Speech, and Language Processing · doi:10.1109/tasl.2007.909282 · Cited by 351
Robustness 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
Self-citationFrom diversity to complexity: Microbial networks in soils
Guseva, K., Darcy, S., Simon, E., Alteio, L. V., Montesinos-Navarro, A., & Kaiser, C. (2022) · Soil Biology and Biochemistry · doi:10.1016/j.soilbio.2022.108604 · Cited by 349
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
Community detection in social networks
Bedi, P., & Sharma, C. (2016) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1178 · Cited by 346
Extending the definition of modularity to directed graphs with overlapping communities
Nicosia, V, Mangioni, G., Carchiolo, V, & Malgeri, M. (2009) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2009/03/p03024 · 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
Equivalence between modularity optimization and maximum likelihood methods for community detection
Newman, M. E. J. (2016) · Physical Review E · doi:10.1103/physreve.94.052315 · Cited by 344
Self-citationA survey of community search over big graphs
Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., & Lin, X. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00556-x · Cited by 339
Shibata, N., Kajikawa, Y., Takeda, Y., & Matsushima, K. (2008) · Technovation · doi:10.1016/j.technovation.2008.03.009 · Cited by 338
Kovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
Modularity-maximizing graph communities via mathematical programming
Agarwal, G., & Kempe, D. (2008) · The European Physical Journal B · doi:10.1140/epjb/e2008-00425-1 · Cited by 338
A model-based approach to attributed graph clustering
Xu, Z., Ke, Y., Wang, Y., Cheng, H., & Cheng, J. (2012) · Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2213836.2213894 · Cited by 332
Size reduction of complex networks preserving modularity
Arenas, A., Duch, J., Fernández, A., & Gómez, S. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/176 · Cited by 330
Camacho, D., Panizo-LLedot, Á., Bello-Orgaz, G., Gonzalez-Pardo, A., & Cambria, E. (2020) · Information Fusion · doi:10.1016/j.inffus.2020.05.009 · Cited by 329
Secundo, G., Ndou, V., Vecchio, P. D., & De Pascale, G. (2020) · Technological Forecasting and Social Change · doi:10.1016/j.techfore.2020.119917 · Cited by 324
Mining communities and their relationships in blogs: A study of online hate groups
Chau, M., & Xu, J. (2007) · International Journal of Human-Computer Studies · doi:10.1016/j.ijhcs.2006.08.009 · Cited by 323
Chen, B., Li, J. S., Wu, X. F., Han, M. Y., Zeng, L., Li, Z., & Chen, G. Q. (2018) · Applied Energy · doi:10.1016/j.apenergy.2017.10.113 · Cited by 315
Vandenbroucke, L., Weeda, W., Lee, N., Baeyens, D., Westfall, J., Figner, B., & Huizinga, M. (2018) · Frontiers in Psychology · doi:10.3389/fpsyg.2018.01572 · Cited by 315
Creating an academic landscape of sustainability science: an analysis of the citation network
Kajikawa, Y., Ohno, J., Takeda, Y., Matsushima, K., & Komiyama, H. (2007) · Sustainability Science · doi:10.1007/s11625-007-0027-8 · Cited by 312
A New Measure of Centrality for Brain Networks
Joyce, K. E., Laurienti, P. J., Burdette, J. H., & Hayasaka, S. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012200 · Cited by 310
An analysis of social network-based Sybil defenses
Viswanath, B., Post, A., Gummadi, K. P., & Mislove, A. (2010) · Proceedings of the ACM SIGCOMM 2010 conference · doi:10.1145/1851182.1851226 · Cited by 304
An Algorithm to Find Overlapping Community Structure in Networks
Gregory, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74976-9_12 · Cited by 302
Community Detection via Maximization of Modularity and Its Variants
Chen, M., Kuzmin, K., & Szymanski, B. K. (2014) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2014.2307458 · Cited by 301
Metrics for Community Analysis: A Survey
Chakraborty, T., Dalmia, A., Mukherjee, A., & Ganguly, N. (2018) · ACM Computing Surveys · doi:10.1145/3091106 · Cited by 296
Method to find community structures based on information centrality
Fortunato, S., Latora, V., & Marchiori, M. (2004) · Physical Review E · doi:10.1103/physreve.70.056104 · Cited by 294
Shen, C.-W., & Ho, J.-T. (2020) · Computers in Human Behavior · doi:10.1016/j.chb.2019.106177 · Cited by 283
Community Detection in Complex Networks Using Genetic Algorithms
Tasgin, M., Herdağdelen, A., & Bingol, H. O. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0711.0491 · Cited by 275
Characterizing the Community Structure of Complex Networks
Lancichinetti, A., Kivelä, M., Saramäki, J., & Fortunato, S. (2010) · PLoS ONE · doi:10.1371/journal.pone.0011976 · Cited by 267
Deep Autoencoder-like Nonnegative Matrix Factorization for Community Detection
Ye, F., Chen, C., & Zheng, Z. (2018) · Proceedings of the 27th ACM International Conference on Information and Knowledge Management · doi:10.1145/3269206.3271697 · Cited by 263
Liang, X., Zou, Q., He, Y., & Yang, Y. (2016) · Cerebral Cortex · doi:10.1093/cercor/bhu316 · Cited by 261
A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L
Yoo, A., Chow, E., Henderson, K., McLendon, W., Hendrickson, B., & Catalyurek, U. (2005) · ACM/IEEE SC 2005 Conference (SC'05) · doi:10.1109/sc.2005.4 · Cited by 261
Analysis of community structure in networks of correlated data
Gómez, S., Jensen, P., & Arenas, A. (2009) · Physical Review E · doi:10.1103/physreve.80.016114 · Cited by 260
Communities and Emerging Semantics in Semantic Link Network: Discovery and Learning
Zhuge, H. (2009) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2008.141 · Cited by 259
Persistent Brain Network Homology From the Perspective of Dendrogram
Lee, H., Kang, H., Chung, M. K., Kim, B.-N., & Lee, D. S. (2012) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2012.2219590 · Cited by 258
Song, J., Birn, R. M., Boly, M., Meier, T. B., Nair, V. A., Meyerand, M. E., & Prabhakaran, V. (2014) · Brain Connectivity · doi:10.1089/brain.2014.0286 · Cited by 258
Lupu, Y., & Voeten, E. (2012) · British Journal of Political Science · doi:10.1017/s0007123411000433 · Cited by 256
Genomic patterns of pleiotropy and the evolution of complexity
Wang, Z., Liao, B.-Y., & Zhang, J. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1004666107 · Cited by 256
Tracking emerging technologies in energy research: Toward a roadmap for sustainable energy
Kajikawa, Y., Yoshikawa, J., Takeda, Y., & Matsushima, K. (2008) · Technological Forecasting and Social Change · doi:10.1016/j.techfore.2007.05.005 · Cited by 255
Towards a new approach to reveal dynamical organization of the brain using topological data analysis
Saggar, M., Sporns, O., Gonzalez-Castillo, J., Bandettini, P. A., Carlsson, G., Glover, G., & Reiss, A. L. (2018) · Nature Communications · doi:10.1038/s41467-018-03664-4 · Cited by 253
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
Demographic structure and pathogen dynamics on the network of livestock movements in Great Britain
Kao, R. R., Danon, L., Green, D. M., & Kiss, I. Z. (2006) · Proceedings of the Royal Society B: Biological Sciences · doi:10.1098/rspb.2006.3505 · Cited by 252
Vértes, P. E., & Bullmore, E. T. (2015) · Journal of Child Psychology and Psychiatry · doi:10.1111/jcpp.12365 · Cited by 197
Sustainability science: the changing landscape of sustainability research
Kajikawa, Y., Tacoa, F., & Yamaguchi, K. (2014) · Sustainability Science · doi:10.1007/s11625-014-0244-x · Cited by 204
A Systematic Empirical Comparison of Different Approaches for Normalizing Citation Impact Indicators
Waltman, L., & van Eck, N. J. (2013) · Journal of Informetrics · doi:10.1016/j.joi.2013.08.002 · Cited by 153
Dynamic network structure of interhemispheric coordination
Doron, K. W., Bassett, D. S., & Gazzaniga, M. S. (2012) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1216402109 · Cited by 153
Uehara, T., Yamasaki, T., Okamoto, T., Koike, T., Kan, S., Miyauchi, S., Kira, J.-I., & Tobimatsu, S. (2014) · Cerebral Cortex · doi:10.1093/cercor/bht004 · Cited by 136
Pereira, J. B., Mijalkov, M., Kakaei, E., Mecocci, P., Vellas, B., Tsolaki, M., Kłoszewska, I., Soininen, H., Spenger, C., Lovestone, S., et al. (2016) · Cerebral Cortex · doi:10.1093/cercor/bhw128 · Cited by 142
Han, K., Mac Donald, C. L., Johnson, A. M., Barnes, Y., Wierzechowski, L., Zonies, D., Oh, J., Flaherty, S., Fang, R., Raichle, M. E., et al. (2014) · NeuroImage · doi:10.1016/j.neuroimage.2013.08.017 · Cited by 123
A 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
“Fast modularity scales up the ability of a previous greedy algorithm (Newman, 2004b) for use on matrices as large as 10 million (Clauset et al., 2004).”
BackgroundMethodBlockchain technology in the smart city: A bibliometric review
Rejeb, A., Rejeb, K., Simske, S. J., & Keogh, J. G. (2022) · Quality & Quantity · doi:10.1007/s11135-021-01251-2 · Cited by 104
“This algorithm minimizes the distance between connected nodes, i.e., keywords (Newman 2004; Noack 2007).”
BackgroundMethodDynamic causal brain circuits during working memory and their functional controllability
Cai, W., Ryali, S., Pasumarthy, R., Talasila, V., & Menon, V. (2021) · Nature Communications · doi:10.1038/s41467-021-23509-x · Cited by 105
Structural network analysis of brain development in young preterm neonates
Brown, C. J., Miller, S. P., Booth, B. G., Andrews, S., Chau, V., Poskitt, K. J., & Hamarneh, G. (2014) · NeuroImage · doi:10.1016/j.neuroimage.2014.07.030 · Cited by 103
Landon, B. E., Keating, N. L., Onnela, J.-P., Zaslavsky, A. M., Christakis, N. A., & O’Malley, A. J. (2018) · JAMA Internal Medicine · doi:10.1001/jamainternmed.2017.5034 · Cited by 99
Huang, P.-Y., Pan, S. L., & Ouyang, T. H. (2014) · European Journal of Information Systems · doi:10.1057/ejis.2014.4 · Cited by 95
Detecting multiple communities using quantum annealing on the D-Wave system
Negre, C. F. A., Ushijima-Mwesigwa, H., & Mniszewski, S. M. (2020) · PLOS ONE · doi:10.1371/journal.pone.0227538 · Cited by 80
“Several algorithms have been proposed based on greedy techniques [13, 14], simulated annealing [15, 16], genetic algorithm [17], spectral optimization [18] and extreme optimization methods [19, 20].”
MethodMapping the multiscale structure of biological systems
Schaffer, L. V., & Ideker, T. (2021) · Cell Systems · doi:10.1016/j.cels.2021.05.012 · Cited by 75
Hart, M. G., Ypma, R. J. F., Romero-Garcia, R., Price, S. J., & Suckling, J. (2016) · Journal of Neurosurgery · doi:10.3171/2015.4.jns142683 · Cited by 74
Bohland, J. W., Saperstein, S., Pereira, F., Rapin, J., & Grady, L. (2012) · Frontiers in Systems Neuroscience · doi:10.3389/fnsys.2012.00078 · Cited by 64
Lohse, C., Bassett, D. S., Lim, K. O., & Carlson, J. M. (2014) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003712 · Cited by 62
“Assuming node i is assigned to community ci and node j is assigned to community cj , the quality of a partition for a binary network is defined using a modularity index [18,19,39,40,41]:”
MethodGenerative models of rich clubs in Hebbian neuronal networks and large-scale human brain networks
Vértes, P. E., Alexander-Bloch, A., & Bullmore, E. T. (2014) · Philosophical Transactions of the Royal Society B: Biological Sciences · doi:10.1098/rstb.2013.0531 · Cited by 50
Community Detection in Quantum Complex Networks
Faccin, M., Migdał, P., Johnson, T. H., Bergholm, V., & Biamonte, J. D. (2014) · Physical Review X · doi:10.1103/physrevx.4.041012 · Cited by 43
“A type of measure that is often used to quantify the quality of a community partitioning choice for this purpose is modularity [40–42], denoted Q .”
BackgroundIdeological biases in social sharing of online information about climate change
Cann, T. J. B., Weaver, I. S., & Williams, H. T. P. (2021) · PLOS ONE · doi:10.1371/journal.pone.0250656 · Cited by 38
Using Machine Learning to Measure Relatedness Between Genes: A Multi-Features Model
Wang, Y., Yang, S., Zhao, J., Du, W., Liang, Y., Wang, C., Zhou, F., Tian, Y., & Ma, Q. (2019) · Scientific Reports · doi:10.1038/s41598-019-40780-7 · Cited by 26
Community detection in network neuroscience
Betzel, R. F. (2020) · arXiv · doi:10.48550/arxiv.2011.06723 · Cited by 24
Gürbüz, B. N., Pastrana, L. M., Pereira, R. N., & Cerqueira, M. A. (2025) · Foods · doi:10.3390/foods14030498 · Cited by 17
Yasui, S., & Idani, G. (2022) · Animal Behavior and Cognition · doi:10.26451/abc.09.01.08.2022 · Cited by 2
Metadata
- Authors
- Newman, M. E. J.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2004-06-18
- Volume
- 69
- Issue
- 6
- Pages
- 066133-066133
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W2089458547
- Cited by
- 5,406
- References
- 23
- FWCI
- 52.31
- Type
- journal article
- Language
- en
- Open access
- green
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.