Finding community structure in very large networks
Open accessAbstract
The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O (md log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m approximately n and d approximately log n, in which case our algorithm runs in essentially linear time, O (n log(2) n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web site of a large on-line retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400 000 vertices and 2 x 10(6) edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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?
El algoritmo Clauset-Newman-Moore busca grupos de vértices que estén conectados densamente entre ellos y que posean pocas conexiones con otros grupos.
“Dicho algoritmo busca grupos de vértices que estén conectados densamente entre ellos y que posean pocas conexiones con otros grupos (Clauset et al., 2004;Mendes Rodrigues et al., 2011).”
From “Vital testimonio confirm󔦔: Polarización de fuentes y redes en el Caso Catrillanca en Twitter (2021) · cites this paper as Clauset et al., 2004
El algoritmo Clauset-Newman-Moore fue seleccionado porque maneja de manera adecuada los recursos computacionales cuando se trata de redes grandes de más de 10 mil relaciones.
“El algoritmo fue seleccionado porque maneja de manera adecuada los recursos computacionales cuando se trata de redes grandes de más de 10 mil relaciones (Hansen et al., 2019;Clauset et al., 2004).”
From “Vital testimonio confirm󔦔: Polarización de fuentes y redes en el Caso Catrillanca en Twitter (2021) · cites this paper as Clauset et al., 2004
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557 · see citing works
Finding 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 · see citing works
Self-citation
Flagged first, then by citations
Research works printed but not linked: 18
- [4]M. E. J. Newman, The structure and function of complex networks. SIAM Review 45 , 167-256 (2003).
- [5]M. Faloutsos, P. Faloutsos, and C. Faloutsos, On powerlaw relationships of the internet topology. Computer Communications Review 29 , 251-262 (1999).
- [7]J. M. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, The Web as a graph: Measurements, models and methods. In Proceedings of the International Conference on Combinatorics and Computing , number 1627 in Lecture Notes in Computer Science, pp. 1-18, Springer, Berlin (1999).
- [8]S. Wasserman and K. Faust, Social Network Analysis . Cambridge University Press, Cambridge (1994).
- [11]J. A. Dunne, R. J. Williams, and N. D. Martinez, Foodweb structure and network theory: The role of connectance and size. Proc. Natl. Acad. Sci. USA 99 , 1291712922 (2002).
- [13]T. Ito, T. Chiba, R. Ozawa, M. Yoshida, M. Hattori, and Y. Sakaki, A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc. Natl. Acad. Sci. USA 98 , 4569-4574 (2001).
- [15]B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 49 , 291-307 (1970).
- [18]J. Scott, Social Network Analysis: A Handbook . Sage, London, 2nd edition (2000).
- [20]M. Girvan and M. E. J. Newman, Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99 , 7821-7826 (2002).
- [22]M. T. Gastner and M. E. J. Newman, Diffusion-based method for producing density equalizing maps. Proc. Natl. Acad. Sci. USA 101 , 7499-7504 (2004).
- [25]P. Holme and M. Huss, Discovery and analysis of biochemical subnetwork hierarchies. In R. Gauges, U. Kummer, J. Pahle, and U. Rost (eds.), Proceedings of the 3rd Workshop on Computation of Biochemical Pathways and Genetic Networks , pp. 3-9, Logos, Berlin (2003).
- [26]J. R. Tyler, D. M. Wilkinson, and B. A. Huberman, Email as spectroscopy: Automated discovery of community structure within organizations. In M. Huysman, E. Wenger, and V. Wulf (eds.), Proceedings of the First International Conference on Communities and Technologies , Kluwer, Dordrecht (2003).
- [28]M. Bogu˜ n´ a, R. Pastor-Satorras, A. D´ ıaz-Guilera, and A. Arenas, Emergence of clustering, correlations, and communities in a social network model. Preprint condmat/0309263 (2003).
- [29]D. M. Wilkinson and B. A. Huberman, A method for finding communities of related genes. Proc. Natl. Acad. Sci. USA 101 , 5241-5248 (2004).
- [31]F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA 101 , 2658-2663 (2004).
- [34]M. E. J. Newman, Analysis of weighted networks. Preprint cond-mat/0407503 (2004). · arXiv
- [35]T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms . MIT Press, Cambridge, MA, 2nd edition (2001).
- [37]G. W. Flake, S. R. Lawrence, C. L. Giles, and F. M. Coetzee, Self-organization and identification of Web communities. IEEE Computer 35 , 66-71 (2002).
Cited by
Sorted by citations
Modularity 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 · see citing works
Self-citationFortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · see citing works
From 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 · see citing works
Resolution limit in community detection
Fortunato, S., & Barthélemy, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0605965104 · Cited by 3,024 · see citing works
Critical phenomena in complex networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1275 · Cited by 2,220 · see citing works
Hierarchical structure and the prediction of missing links in networks
Clauset, A., Moore, C., & Newman, M. E. J. (2008) · Nature · doi:10.1038/nature06830 · Cited by 2,171 · see citing works
Self-citationGreen supply chain management: A review and bibliometric analysis
Fahimnia, B., Sarkis, J., & Davarzani, H. (2015) · International Journal of Production Economics · doi:10.1016/j.ijpe.2015.01.003 · Cited by 2,131 · see citing works
Microbial co-occurrence relationships in the human microbiome
Faust, K., Sathirapongsasuti, J. F., Izard, J., Segata, N., Gevers, D., Raes, J., & Huttenhower, C. (2012) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002606 · Cited by 1,527 · see citing works
Sporns, O., & Betzel, R. F. (2016) · Annual Review of Psychology · doi:10.1146/annurev-psych-122414-033634 · Cited by 1,334 · see citing works
Performance of modularity maximization in practical contexts
Good, B. H., de Montjoye, Y.-A., & Clauset, A. (2010) · Physical Review E · doi:10.1103/physreve.81.046106 · Cited by 937 · see citing works
Self-citationSocial big data: recent achievements and new challenges
Bello-Orgaz, G., Jung, J. J., & Camacho, D. (2016) · Information Fusion · doi:10.1016/j.inffus.2015.08.005 · Cited by 846 · see citing works
Age-related changes in modular organization of human brain functional networks
Meunier, D., Achard, S., Morcom, A., & Bullmore, E. (2009) · NeuroImage · doi:10.1016/j.neuroimage.2008.09.062 · Cited by 756 · see citing works
Mapping the NFT revolution: Market trends, trade networks, and visual features
Nadini, M., Alessandretti, L., Di Giacinto, F., Martino, M., Aiello, L. M., & Baronchelli, A. (2021) · Scientific Reports · doi:10.1038/s41598-021-00053-8 · Cited by 715 · see citing works
Science vs Conspiracy: Collective Narratives in the Age of Misinformation
Bessi, A., Coletto, M., Davidescu, G. A., Scala, A., Caldarelli, G., & Quattrociocchi, W. (2015) · PLOS ONE · doi:10.1371/journal.pone.0118093 · Cited by 645 · see citing works
Personalization in personalized marketing: Trends and ways forward
Chandra, S., Verma, S., Lim, W. M., Kumar, S., & Donthu, N. (2022) · Psychology & Marketing · doi:10.1002/mar.21670 · Cited by 595 · see citing works
Alexander-Bloch, A. F., Gogtay, N., Meunier, D., Birn, R., Clasen, L., Lalonde, F., Lenroot, R., Giedd, J., & Bullmore, E. T. (2010) · Frontiers in Systems Neuroscience · doi:10.3389/fnsys.2010.00147 · Cited by 480 · see citing works
Chen, Z. J., He, Y., Rosa-Neto, P., Germann, J., & Evans, A. C. (2008) · Cerebral Cortex · doi:10.1093/cercor/bhn003 · Cited by 484 · see citing works
Polarization of the vaccination debate on Facebook
Schmidt, A. L., Zollo, F., Scala, A., Betsch, C., & Quattrociocchi, W. (2018) · Vaccine · doi:10.1016/j.vaccine.2018.05.040 · Cited by 403 · see citing works
The Paradigm-Shift of Social Spambots: Evidence, Theories, and Tools for the Arms Race
Cresci, S., Di Pietro, R., Petrocchi, M., Spognardi, A., & Tesconi, M. (2017) · Proceedings of the 26th International Conference on World Wide Web Companion - WWW '17 Companion · doi:10.1145/3041021.3055135 · Cited by 381 · see citing works
Big Data and supply chain management: A review and bibliometric analysis
Mishra, D., Gunasekaran, A., Papadopoulos, T., & Childe, S. J. (2018) · Annals of Operations Research · doi:10.1007/s10479-016-2236-y · Cited by 382 · see citing works
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 · see citing works
Self-citationKaralunas, S. L., Fair, D., Musser, E. D., Aykes, K., Iyer, S. P., & Nigg, J. T. (2014) · JAMA Psychiatry · doi:10.1001/jamapsychiatry.2014.763 · Cited by 340 · see citing works
RetractedAsymmetric ideological segregation in exposure to political news on Facebook
González-Bailón, S., Lazer, D., Barberá, P., Zhang, M., Allcott, H., Brown, T., Crespo-Tenorio, A., Freelon, D., Gentzkow, M., Guess, A. M., et al. (2023) · Science · doi:10.1126/science.ade7138 · Cited by 315 · see citing works
Anatomy of news consumption on Facebook
Schmidt, A. L., Zollo, F., Del Vicario, M., Bessi, A., Scala, A., Caldarelli, G., Stanley, H. E., & Quattrociocchi, W. (2017) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1617052114 · Cited by 305 · see citing works
Wampach, L., Heintz-Buschart, A., Fritz, J. V., Ramiro-Garcia, J., Habier, J., Herold, M., Narayanasamy, S., Kaysen, A., Hogan, A. H., Bindl, L., et al. (2018) · Nature Communications · doi:10.1038/s41467-018-07631-x · Cited by 292 · see citing works
Wan, Y.-W., Al-Ouran, R., Mangleburg, C. G., Perumal, T. M., Lee, T. V., Allison, K., Swarup, V., Funk, C. C., Gaiteri, C., Allen, M., et al. (2020) · Cell Reports · doi:10.1016/j.celrep.2020.107908 · Cited by 295 · see citing works
“, 2015), a fast greedy algorithm (Clauset et al., 2004), InfoMap (Rosvall and Bergstrom, 2008), LinkCommunities (Ahn et al.”
MethodAlexa, what do we know about conversational commerce? Insights from a systematic literature review.
Lim, W. M., Kumar, S., Verma, S., & Chaturvedi, R. (2022) · Psychology & Marketing · doi:10.1002/mar.21654 · Cited by 293 · see citing works
Sebestyén, E., Singh, B., Miñana, B., Pagès, A., Mateo, F., Pujana, M. A., Valcárcel, J., & Eyras, E. (2016) · Genome Research · doi:10.1101/gr.199935.115 · Cited by 276 · see citing works
Developmental Changes in Organization of Structural Brain Networks
Khundrakpam, B. S., Reid, A., Brauer, J., Carbonell, F., Lewis, J., Ameis, S., Karama, S., Lee, J., Chen, Z., Das, S., et al. (2013) · Cerebral Cortex · doi:10.1093/cercor/bhs187 · Cited by 234 · see citing works
Brain anatomical networks in early human brain development
Fan, Y., Shi, F., Smith, J. K., Lin, W., Gilmore, J. H., & Shen, D. (2011) · NeuroImage · doi:10.1016/j.neuroimage.2010.07.025 · Cited by 225 · see citing works
Ferreira, P. G., Jares, P., Rico, D., Gómez-López, G., Martínez-Trillos, A., Villamor, N., Ecker, S., González-Pérez, A., Knowles, D. G., Monlong, J., et al. (2014) · Genome Research · doi:10.1101/gr.152132.112 · Cited by 214 · see citing works
Structural Information and Dynamical Complexity of Networks
Li, A., & Pan, Y. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2555904 · Cited by 200 · see citing works
Development Trends of White Matter Connectivity in the First Years of Life
Yap, P.-T., Fan, Y., Chen, Y., Gilmore, J. H., Lin, W., & Shen, D. (2011) · PLoS ONE · doi:10.1371/journal.pone.0024678 · Cited by 190 · see citing works
Emergency information diffusion on online social media during storm Cindy in U.S.
Kim, J., Bae, J., & Hastak, M. (2018) · International Journal of Information Management · doi:10.1016/j.ijinfomgt.2018.02.003 · Cited by 166 · see citing works
Network Analysis Reveals Increased Integration during Emotional and Motivational Processing
Kinnison, J., Padmala, S., Choi, J.-M., & Pessoa, L. (2012) · Journal of Neuroscience · doi:10.1523/jneurosci.0821-12.2012 · Cited by 153 · see citing works
The dynamics of social networks among female Asian elephants
de Silva, S., Ranjeewa, A. D., & Kryazhimskiy, S. (2011) · BMC Ecology · doi:10.1186/1472-6785-11-17 · Cited by 159 · see citing works
A Comparison of Social Organization in Asian Elephants and African Savannah Elephants
de Silva, S., & Wittemyer, G. (2012) · International Journal of Primatology · doi:10.1007/s10764-011-9564-1 · Cited by 134 · see citing works
Falling into the Echo Chamber: The Italian Vaccination Debate on Twitter
Cossard, A., De Francisci Morales, G., Kalimeri, K., Mejova, Y., Paolotti, D., & Starnini, M. (2020) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v14i1.7285 · Cited by 126 · see citing works
The role of Internet of Things in food supply chain quality management: A review
Ben-Daya, M., Hassini, E., Bahroun, Z., & Banimfreg, B. H. (2021) · Quality Management Journal · doi:10.1080/10686967.2020.1838978 · Cited by 120 · see citing works
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 · see citing works
“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).”
MethodEllis, N. C., O'Donnell, M. B., & Römer, U. (2014) · Cognitive Linguistics · doi:10.1515/cog-2013-0031 · Cited by 113 · see citing works
Spontaneous emergence of modularity in cellular networks
Solé, R. V., & Valverde, S. (2008) · Journal of The Royal Society Interface · doi:10.1098/rsif.2007.1108 · Cited by 102 · see citing works
Detection of malicious social bots: A survey and a refined taxonomy
Latah, M. (2020) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113383 · Cited by 94 · see citing works
Wang, H., Li, Y., Ryder, J. W., Hole, J. T., Ebert, P. J., Airey, D. C., Qian, H.-R., Logsdon, B., Fisher, A., Ahmed, Z., et al. (2018) · Molecular Neurodegeneration · doi:10.1186/s13024-018-0296-y · Cited by 83 · see citing works
Inferring Strange Behavior from Connectivity Pattern in Social Networks
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-06608-0_11 · Cited by 82 · see citing works
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 · see citing works
Graph theoretical analysis of developmental patterns of the white matter network
Chen, Z., Liu, M., Gross, D. W., & Beaulieu, C. (2013) · Frontiers in Human Neuroscience · doi:10.3389/fnhum.2013.00716 · Cited by 77 · see citing works
Putting <i>AlphaFold</i> models to work with <i>phenix.process_predicted_model</i> and <i>ISOLDE</i>
Oeffner, R. D., Croll, T. I., Millán, C., Poon, B. K., Schlicksup, C. J., Read, R. J., & Terwilliger, T. C. (2022) · Acta Crystallographica Section D Structural Biology · doi:10.1107/s2059798322010026 · Cited by 63 · see citing works
A data-driven approach to post-stroke aphasia classification and lesion-based prediction
Landrigan, J.-F., Zhang, F., & Mirman, D. (2021) · Brain · doi:10.1093/brain/awab010 · Cited by 54 · see citing works
Inferring lockstep behavior from connectivity pattern in large graphs
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2016) · Knowledge and Information Systems · doi:10.1007/s10115-015-0883-y · Cited by 43 · see citing works
Himelboim, I., & Golan, G. J. (2023) · Journal of Interactive Advertising · doi:10.1080/15252019.2022.2139653 · Cited by 42 · see citing works
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 · see citing works
Homophily and polarization on political twitter during the 2017 Norwegian election
Enjolras, B., & Salway, A. (2022) · Social Network Analysis and Mining · doi:10.1007/s13278-022-01018-z · Cited by 22 · see citing works
Fragmented sleep relates to hallucinations across perceptual modalities in the general population
Brederoo, S. G., de Boer, J. N., de Vries, J., Linszen, M. M. J., & Sommer, I. E. C. (2021) · Scientific Reports · doi:10.1038/s41598-021-87318-4 · Cited by 18 · see citing works
On the adoption and impact of predictive analytics for server incident reduction
Giurgiu, I., Wiesmann, D., Bogojeska, J., Lanyi, D., Stark, G., Wallace, R. B., Pereira, M. M., & Hidalgo, A. A. (2017) · IBM Journal of Research and Development · doi:10.1147/jrd.2016.2631400 · Cited by 17 · see citing works
Rosenkrantz, J. T., Aarts, H., Abee, T., Rolfe, M. D., Knudsen, G. M., Nielsen, M.-B., Thomsen, L. E., Zwietering, M. H., Olsen, J. E., & Pin, C. (2013) · BMC Microbiology · doi:10.1186/1471-2180-13-294 · Cited by 13 · see citing works
“Vital testimonio confirm󔦔: Polarización de fuentes y redes en el Caso Catrillanca en Twitter
Santos, M. L. B., Jaramillo Castro, O., & Aguirre, D. (2021) · Cuadernos.info · doi:10.7764/cdi.49.27509 · Cited by 7 · see citing works
“El algoritmo fue seleccionado porque maneja de manera adecuada los recursos computacionales cuando se trata de redes grandes de más de 10 mil relaciones (Hansen et al., 2019; Clauset et al., 2004).”
BackgroundArtificial Intelligence Chatbots Mimic Human Collective Behaviour
He, J., Wallis, F., Gvirtz, A., & Rathje, S. (2024) · doi:10.21203/rs.3.rs-3096289/v2 · Cited by 4 · see citing works
- Authors
- Clauset, A., Newman, M. E. J., & Moore, C.
- Affiliations
- University of New Mexico (US)
- University of Michigan (US)
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2004-12-06
- Volume
- 70
- Issue
- 6
- Pages
- 066111-066111
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W2047940964
- Cited by
- 7,390
- References
- 2
- Citations by year
- 2026: 240 · 2025: 367 · 2024: 460 · 2023: 414 · 2022: 515 · 2021: 546 · 2020: 556 · 2019: 478 · 2018: 504 · 2017: 438 · 2016: 472 · 2015: 378 · 2014: 393 · 2013: 361 · 2012: 305
- FWCI
- 30.91
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review E (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
- Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Complex Systems and Time Series Analysis
- Keywords
- community detection, large-scale networks, sparse networks, dendrogram, linear-time algorithms, customer purchasing patterns
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
