The DOI matches its Crossref record; 71 of the 71 references it cites were found in a registry or an index.
Finding community structure in networks using the eigenvectors of matrices
Open accessAbstract
We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.
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
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Granovetter, M. S. (1973) · American Journal of Sociology · doi:10.1086/225469 · Cited by 40,491
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
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
Self-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
Self-citationModularity and community structure in networks
Newman, M. E. J. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0601602103 · Cited by 12,256
Self-citationComplex networks: structure and dynamics
BOCCALETTI, S., LATORA, V, MORENO, Y., CHAVEZ, M., & HWANG, D. (2006) · Physics Reports · doi:10.1016/j.physrep.2005.10.009 · Cited by 11,010
A Set of Measures of Centrality Based on Betweenness
Freeman, L. C. (1977) · Sociometry · doi:10.2307/3033543 · Cited by 10,295
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Strogatz, S. H. (2001) · Nature · doi:10.1038/35065725 · Cited by 8,302
Finding 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
Self-citationChung, 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
Self-citationUncovering the overlapping community structure of complex networks in nature and society
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005) · Nature · doi:10.1038/nature03607 · Cited by 5,373 · cited 2×
“Social networks [5], biochemical networks [7, 8, 9], and information networks such as the web [10], have all been shown to possess strong community structure, a finding that has substantial practical implications for our understanding of the systems these networks represent.”
BackgroundAn 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
Assortative Mixing in Networks
Newman, M. E. J. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.208701 · Cited by 4,988
Self-citationFunctional cartography of complex metabolic networks
Guimerà, R., & Nunes Amaral, L. A. (2005) · Nature · doi:10.1038/nature03288 · Cited by 3,983
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 3,977
Bollobás, B. (1998) · Graduate Texts in Mathematics · doi:10.1007/978-1-4612-0619-4 · Cited by 3,772
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2001) · Physical Review E · doi:10.1103/physreve.64.026118 · Cited by 3,648
Self-citationMatrix Analysis and Applied Linear Algebra
Meyer, C. (2000) · doi:10.1137/1.9780898719512 · Cited by 3,565
Matrix analysis and applied linear algebra
(2001) · Choice Reviews Online · doi:10.5860/choice.38-5065 · Cited by 3,300
Dorogovtsev, S. N., & Mendes, J. F. F. (2002) · Advances in Physics · doi:10.1080/00018730110112519 · Cited by 3,171
Newman, M. E. J. (2003) · Physical Review E · doi:10.1103/physreve.67.026126 · Cited by 3,087
Self-citationClasses of small-world networks
Amaral, L. A. N., Scala, A., Barthélémy, M., & Stanley, H. E. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.200327197 · Cited by 3,051
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
Newman, M. E. J. (2004) · Physical Review E · doi:10.1103/physreve.70.056131 · Cited by 2,476
Self-citationDefining 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×
“A huge variety of community detection techniques have been developed, based variously on centrality measures, flow models, random walks, resistor networks, optimization, and many other approaches [5, 8, 9, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35].”
BackgroundA critical point for random graphs with a given degree sequence
Molloy, M., & Reed, B. (1995) · Random Structures & Algorithms · doi:10.1002/rsa.3240060204 · Cited by 2,351
Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003) · Behavioral Ecology and Sociobiology · doi:10.1007/s00265-003-0651-y · Cited by 2,277
The Structure and Dynamics of Networks
Newman, M., Barabási, A.-L., & Watts, D. J. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356 · Cited by 2,268
Self-citationStatistical mechanics of community detection
Reichardt, J., & Bornholdt, S. (2006) · Physical Review E · doi:10.1103/physreve.74.016110 · Cited by 2,048
Computing Communities in Large Networks Using Random Walks
Pons, P., & Latapy, M. (2005) · Lecture Notes in Computer Science · doi:10.1007/11569596_31 · Cited by 2,048
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
Synchronization in Small-World Systems
Barahona, M., & Pecora, L. M. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.054101 · Cited by 1,638
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · doi:10.1093/acprof:oso/9780198515906.001.0001 · Cited by 1,563
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
The Structure and Dynamics of Networks
Boguñá, M. (2007) · Journal of Statistical Physics · doi:10.1007/s10955-006-9267-8 · Cited by 1,485
Dynamical and Correlation Properties of the Internet
Pastor-Satorras, R., Vázquez, A., & Vespignani, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.87.258701 · Cited by 1,466
New spectral methods for ratio cut partitioning and clustering
Hagen, L., & Kahng, A. B. (1992) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.159993 · Cited by 1,288
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
Connected Components in Random Graphs with Given Expected Degree Sequences
Chung, F., & Lu, L. (2002) · Annals of Combinatorics · doi:10.1007/pl00012580 · Cited by 938
Modularity from fluctuations in random graphs and complex networks
Guimerà, R., Sales-Pardo, M., & Amaral, L. A. N. (2004) · Physical Review E · doi:10.1103/physreve.70.025101 · Cited by 894
Heterogeneity in Oscillator Networks: Are Smaller Worlds Easier to Synchronize?
Nishikawa, T., Motter, A. E., Lai, Y.-C., & Hoppensteadt, F. C. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.014101 · Cited by 839
Proceedings. 45th Annual IEEE Symposium on Foundations of Computer Science
(2004) · 45th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.4 · Cited by 805
Compartments revealed in food-web structure.
Krause, A. E., Frank, K. A., Mason, D. M., Ulanowicz, R. E., & Taylor, W. W. (2003) · Nature · doi:10.1038/nature02115 · Cited by 795
Finding local community structure in networks
Clauset, A. (2005) · Physical Review E · doi:10.1103/physreve.72.026132 · Cited by 788
Burt, R. S. (1976) · Social Forces · doi:10.1093/sf/55.1.93 · Cited by 607
Detecting Fuzzy Community Structures in Complex Networks with a Potts Model
Reichardt, J., & Bornholdt, S. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.218701 · Cited by 593
Finding 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
Subnetwork hierarchies of biochemical pathways
Holme, P., Huss, M., & Jeong, H. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg033 · Cited by 367
Bern, M. W., Eppstein, D., & Gilbert, J. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80059-5 · Cited by 350
Detecting communities in large networks
Capocci, A., Servedio, V. D. P., Caldarelli, G., & Colaiori, F. (2005) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2004.12.050 · Cited by 329
Networks of sexual contacts: implications for the pattern of spread of HIV
Gupta, S., Anderson, R. M., & May, R. M. (1989) · AIDS · doi:10.1097/00002030-198912000-00005 · Cited by 299
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
Distance, dissimilarity index, and network community structure
Zhou, H. (2003) · Physical Review E · doi:10.1103/physreve.67.061901 · Cited by 272
Sexual mixing patterns in the spread of gonococcal and chlamydial infections.
Aral, S. O., Hughes, J. P., Stoner, B., Whittington, W., Handsfield, H. H., Anderson, R. M., & Holmes, K. K. (1999) · American Journal of Public Health · doi:10.2105/ajph.89.6.825 · Cited by 271
Spectral measures of bipartivity in complex networks
Estrada, E., & Rodríguez-Velázquez, J. A. (2005) · Physical Review E · doi:10.1103/physreve.72.046105 · Cited by 237
The effect of size heterogeneity on community identification in complex networks
Danon, L., Díaz-Guilera, A., & Arenas, A. (2006) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2006/11/p11010 · Cited by 234
Community detection as an inference problem
Hastings, M. B. (2006) · Physical Review E · doi:10.1103/physreve.74.035102 · Cited by 213
Spectral partitioning: the more eigenvectors, the better
Alpert, C. J., & Yao, S.-Z. (1995) · Proceedings of the 32nd ACM/IEEE conference on Design automation conference - DAC '95 · doi:10.1145/217474.217529 · Cited by 202
Identifying communities within energy landscapes
Massen, C. P., & Doye, J. P. K. (2005) · Physical Review E · doi:10.1103/physreve.71.046101 · Cited by 176
Zhou, H., & Lipowsky, R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24688-6_137 · Cited by 152
Holme, P., Liljeros, F., Edling, C., & Kim, B. J. (2003) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.68.056107 · Cited by 148
Sexual Mixing Patterns of Patients Attending Sexually Transmitted Diseases Clinics
Garnett, G. P., Hughes, J. P., Anderson, R. M., Stoner, B. P., ARAL, S. O., Whittington, W. L. H., Handsfield, H. H., & Holmes, K. K. (1996) · Sexually Transmitted Diseases · doi:10.1097/00007435-199605000-00015 · Cited by 140
Huss, M., & Holme, P. (2007) · IET Systems Biology · doi:10.1049/iet-syb:20060077 · Cited by 110
Preferential attachment of communities: The same principle, but a higher level
Pollner, P., Palla, G., & Vicsek, T. (2005) · Europhysics Letters (EPL) · doi:10.1209/epl/i2005-10414-6 · Cited by 85
Preferential attachment of communities: the same principle, but a higher levelPreprint
Pollner, P., Palla, G., & Vicsek, T. (2006) · Cited by 72
Comparison and validation of community structures in complex networks
Gustafsson, M., Hörnquist, M., & Lombardi, A. (2006) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2005.12.017 · Cited by 70
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
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).”
BackgroundMethodInfluentialFrom Louvain to Leiden: guaranteeing well-connected communities
Traag, V. A., Waltman, L., & van Eck, N. J. (2019) · Scientific Reports · doi:10.1038/s41598-019-41695-z · Cited by 5,635
Near linear time algorithm to detect community structures in large-scale networks
Raghavan, U. N., Albert, R., & Kumara, S. (2007) · Physical Review E · doi:10.1103/physreve.76.036106 · Cited by 3,502
Molecular ecological network analyses
Deng, Y., Jiang, Y.-H., Yang, Y., He, Z., Luo, F., & Zhou, J. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-113 · Cited by 3,196
Metadata
- Authors
- Newman, M. E. J.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2006-09-11
- Volume
- 74
- Issue
- 3
- Pages
- 036104-036104
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W2015953751
- Cited by
- 4,761
- References
- 71
- FWCI
- 57.85
- 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.