Modularity and community structure in networks
Open accessThe DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Abstract
Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as “modularity” over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.
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 source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Independently applying the community detection algorithm to the ADHD cohort shows similar findings to those in A.”
From Distinct neuropsychological subgroups in typically developing youth inform heterogeneity in children with ADHD (2012) · cites this paper as [29]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“One recent study has shown that, even in relatively small networks, a large number of good solutions exist for the standard modularity criterion [51], [52].”
From Spatial Guilds in the Serengeti Food Web Revealed by a Bayesian Group Model (2011) · cites this paper as [51]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Values greater than 0.8 and 0.3, respectively, indicate that the subgroupings are appropriate (Newman, 2004b, 2006).”
From Characteristics of social relationships in a group of captive Asian elephants (Elephas maximus) in the elephant village in Thailand (2022) · cites this paper as Newman, 2006
Experimental — accuracy not yet measuredThe check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“Even if every such network individually disfavors cooperators, transitions between them can facilitate the evolution of cooperation - a result that is reminiscent of Parrondo's paradox [50].”
From Strategy evolution on dynamic networks (2023) · cites this paper as [50]
Experimental — accuracy not yet measuredIn the citing paper
“The Newman algorithm [19], as applied here, is widely used, but is likely not optimal for all situations.”
From Organizing Heterogeneous Samples Using Community Detection of GIMME-Derived Resting State Functional Networks (2014) · cites this paper as [19]
1 more claim about this paper
Create a free account to see every claim other papers make about this one.
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
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-citationSocial Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Community 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 3×
“(We note in passing that in principle the fine-tuning method could also be used to refine results from other modularity maximization algorithms, such as the extremal optimization algorithm of ref.”
BackgroundMethodSelf-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 3×
“(We note in passing that in principle the fine-tuning method could also be used to refine results from other modularity maximization algorithms, such as the extremal optimization algorithm of ref.”
BackgroundMethodSelf-citationFinding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390 · cited 1×
“We make such moves repeatedly, with the constraint that each vertex is moved only once.”
BackgroundSelf-citationNetwork motifs: simple building blocks of complex networks.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002) · Science · doi:10.1126/science.298.5594.824 · Cited by 7,368
(2017) · The SAGE Encyclopedia of Communication Research Methods · doi:10.4135/9781483381411.n575 · Cited by 6,008
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Fast algorithm for detecting community structure in networks
Newman, M. E. J. (2004) · Physical Review E · doi:10.1103/physreve.69.066133 · Cited by 5,406 · cited 2×
“A typical problem in graph partitioning is the division of a set of tasks between the processors of a parallel computer so as to minimize the necessary amount of interprocessor communication.”
BackgroundSelf-citationAn Efficient Heuristic Procedure for Partitioning Graphs
Kernighan, B. W., & Lin, S. (1970) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1970.tb01770.x · Cited by 5,305 · cited 1×
“We can, if we want, artificially forbid this solution, but then a division that puts just one vertex in one group and the rest in the other will often be optimal, and so forth.”
BackgroundThe 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
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 · cited 1×
“…of vertices (shaded) within which there are many edges, with only a smaller number of edges between vertices of different groups. www.pnas.org cgi doi 10.1073 pnas.0601602103 PNAS June 6, 2006 vol. 103 no. 23 8577–8582 A PP LI ED M A TH EM A TI CS D ow nl oa de d by g ue st o n Ja nu ar y 3, 2 02 1”
BackgroundInfluentialThe 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-citationFunctional cartography of complex metabolic networks
Guimerà, R., & Nunes Amaral, L. A. (2005) · Nature · doi:10.1038/nature03288 · Cited by 3,983 · cited 2×
“Modularity and community structure in networks”
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 3,977 · cited 1×
“Conflict of interest statement: No conflicts declared.”
Dorogovtsev, S. N., & Mendes, J. F. F. (2002) · Advances in Physics · doi:10.1080/00018730110112519 · Cited by 3,171
Comparing community structure identification
Danon, L., Díaz-Guilera, A., Duch, J., & Arenas, A. (2005) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2005/09/p09008 · Cited by 2,872 · cited 2×
“Modularity and community structure in networks”
The political blogosphere and the 2004 U.S. election: divided they blog
Adamic, L. A., & Glance, N. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134277 · Cited by 2,619
Defining and identifying communities in networks
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0400054101 · Cited by 2,450 · cited 1×
“…of vertices (shaded) within which there are many edges, with only a smaller number of edges between vertices of different groups. www.pnas.org cgi doi 10.1073 pnas.0601602103 PNAS June 6, 2006 vol. 103 no. 23 8577–8582 A PP LI ED M A TH EM A TI CS D ow nl oa de d by g ue st o n Ja nu ar y 3, 2 02 1”
BackgroundInfluentialSocial Structure from Multiple Networks. I. Blockmodels of Roles and Positions
White, H. C., Boorman, S. A., & Breiger, R. L. (1976) · American Journal of Sociology · doi:10.1086/226141 · Cited by 2,097 · cited 1×
“Modularity and community structure in networks”
Detecting community structure in networks
Newman, M. E. J. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00124-y · Cited by 2,028
Self-citationPartitioning Sparse Matrices with Eigenvectors of Graphs
Pothen, A., Simon, H. D., & Liou, K.-P. (1990) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0611030 · Cited by 1,684 · cited 1×
“Conflict of interest statement: No conflicts declared.”
Community detection in complex networks using extremal optimization
Duch, J., & Arenas, A. (2005) · Physical Review E · doi:10.1103/physreve.72.027104 · Cited by 1,549 · cited 3×
“In this section I describe briefly another method for dividing networks in two by modularity optimization, which is entirely different from the spectral method.”
BackgroundMethodSelf-similar community structure in a network of human interactions
Guimerà, R., Danon, L., Díaz-Guilera, A., Giralt, F., & Arenas, A. (2003) · Physical Review E · doi:10.1103/physreve.68.065103 · Cited by 1,515
GLEISER, P. M., & DANON, L. (2003) · Advances in Complex Systems · doi:10.1142/s0219525903001067 · Cited by 1,032
Self-organization and identification of Web communities
Flake, G. W., Lawrence, S., Giles, C. L., & Coetzee, F. M. (2002) · Computer · doi:10.1109/2.989932 · Cited by 1,018 · cited 2×
“…of vertices (shaded) within which there are many edges, with only a smaller number of edges between vertices of different groups. www.pnas.org cgi doi 10.1073 pnas.0601602103 PNAS June 6, 2006 vol. 103 no. 23 8577–8582 A PP LI ED M A TH EM A TI CS D ow nl oa de d by g ue st o n Ja nu ar y 3, 2 02 1”
BackgroundInfluentialScale-free topology of e-mail networks
Ebel, H., Mielsch, L.-I., & Bornholdt, S. (2002) · Physical Review E · doi:10.1103/physreve.66.035103 · Cited by 940
SPECTRAL GRAPH THEORY (CBMS Regional Conference Series in Mathematics 92)
Biggs, N. (1998) · Bulletin of the London Mathematical Society · doi:10.1112/s0024609397223611 · Cited by 433
A Spectral Clustering Approach To Finding Communities in Graphs
White, S., & Smyth, P. (2005) · Proceedings of the 2005 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.25 · Cited by 404
Subnetwork hierarchies of biochemical pathways
Holme, P., Huss, M., & Jeong, H. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg033 · Cited by 367 · cited 1×
“Modularity and community structure in networks”
Graph partitioning - a surveyPreprint
Elsner, U. (2005) · Qucosa (Saxon State and University Library Dresden) · Cited by 73
Macro- and micro-structure of trust networksPreprint
Guardiola, X., Guimerà, R., Arenas, À., Díaz-Guilera, A., Streib, D., & Amaral, L. A. N. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.cond-mat/0206240 · Cited by 58
Research works printed but not linked: 1
- P.-O. Fjällström Linköping Electronic Articles in Computer and Information Science Vol. 3 Available at www.ep.liu.se/ea/cis/1998/006. Accessed May 10 2006. (1998).
Cited by
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424
Complex network measures of brain connectivity: Uses and interpretations
Rubinov, M., & Sporns, O. (2010) · NeuroImage · doi:10.1016/j.neuroimage.2009.10.003 · Cited by 11,522
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
“…methods, which are computationally demanding (Guimerà et al., 2004; Massen and Doye, 2005; Medus et al., 2005); algorithms giving a good tradeoff between high accuracy and low complexity (Duch and Arenas, 2005; Lehmann and Hansen, 2007; Newman, 2006b; Ruan and Zhang, 2007; White and Smyth, 2005).”
BackgroundMethodInfluentialDeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123
“The eigenvectors of B encode information about modular graph partitions of G [34].”
BackgroundThe igraph software package for complex network research
Csárdi, G., & Nepusz, T. (2006) · Medical Entomology and Zoology · Cited by 13,507
Metadata
- Authors
- Newman, M. E. J.
- Affiliations
- University of California, Irvine (US)
- Corresponding author
- Newman, M. E. J.
- ORCID
- Newman, M. E. J.
- Venue
- Proceedings of the National Academy of Sciences
- Publisher
- National Academy of Sciences
- Published
- 2006-06-06
- Volume
- 103
- Issue
- 23
- Pages
- 8577-8582
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W2151936673
- Semantic Scholar
- 2a91c8ff11a828209f10714cfc46fd929a51e9dc
- Cited by
- 12,256
- References
- 33
- Citations by year
- 2026: 644 · 2025: 780 · 2024: 805 · 2023: 806 · 2022: 861 · 2021: 991 · 2020: 911 · 2019: 912 · 2018: 835 · 2017: 734 · 2016: 705 · 2015: 626 · 2014: 597 · 2013: 510 · 2012: 405
- FWCI
- 102.26
- Type
- journal article
- Language
- en
- Open access
- green
- europepmc.org
- Locations
- Proceedings of the National Academy of Sciences (publishedVersion)
- Europe PMC (PubMed Central) (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Bulletin of the American Physical Society
- Funders
- National Science Foundation (0405348)
- James S. McDonnell Foundation
- 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 detection, modularity, modularity matrix, spectral algorithms, eigenvectors, network partitioning, complex networks, social networks, metabolic networks, regulatory 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.