The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Near linear time algorithm to detect community structures in large-scale networks
Open accessAbstract
Community detection and analysis is an important methodology for understanding the organization of various real-world networks and has applications in problems as diverse as consensus formation in social communities or the identification of functional modules in biochemical networks. Currently used algorithms that identify the community structures in large-scale real-world networks require a priori information such as the number and sizes of communities or are computationally expensive. In this paper we investigate a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization of a predefined objective function nor prior information about the communities. In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities. We validate the algorithm by applying it to networks whose community structures are known. We also demonstrate that the algorithm takes an almost linear time and hence it is computationally less expensive than what was possible so far.
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
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
Self-citationStatistical 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
Self-citationThe Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Social 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
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
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
Bollobás, B. (1985) · Cited by 6,196
(2017) · The SAGE Encyclopedia of Communication Research Methods · doi:10.4135/9781483381411.n575 · Cited by 6,008
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 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
“Leung et al. have found that the original algorithm by Raghavan et al., applied on online social networks, often yields partitions with one giant community together with much smaller ones (Leung et al., 2009).”
MethodInfluentialFrom 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
“Trying to fix the problem by simply considering the connected components of communities 19–21 is unsatisfactory because it addresses only the most extreme case and does not resolve the more fundamental problem.”
BackgroundAn 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
Community detection in networks: a user guide
Fortunato, S., & Hric, D. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.09.002 · Cited by 2,086
Fake news on Twitter during the 2016 U.S. presidential election
Grinberg, N., Joseph, K., Friedland, L., Swire-Thompson, B., & Lazer, D. (2019) · Science · doi:10.1126/science.aau2706 · Cited by 1,803
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,872
Kuhl, C., Tautenhahn, R., Böttcher, C., Larson, T. R., & Neumann, S. (2012) · Analytical Chemistry · doi:10.1021/ac202450g · Cited by 1,203
Finding Statistically Significant Communities in Networks
Lancichinetti, A., Radicchi, F., Ramasco, J. J., & Fortunato, S. (2011) · PLoS ONE · doi:10.1371/journal.pone.0018961 · Cited by 1,187
Cooperative Game Theory Approaches for Network Partitioning
Avrachenkov, K. E., Kondratev, A. Y., & Mazalov, V. V. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-62389-4_49 · Cited by 1,073
Overlapping community detection in networks: The state-of-the-art and comparative study
Xie, J., Kelley, S., & Szymanski, B. K. (2013) · ACM Computing Surveys · doi:10.1145/2501654.2501657 · Cited by 930
Overlapping Community Detection in Networks: the State of the Art and Comparative Study
Xie, J., Kelley, S., & Szymanski, B. K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1110.5813 · Cited by 865
Statistical properties of community structure in large social and information networks
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367591 · Cited by 860
Finding overlapping communities in networks by label propagation
Gregory, S. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/10/103018 · Cited by 806
Consensus clustering in complex networks
Lancichinetti, A., & Fortunato, S. (2012) · Scientific Reports · doi:10.1038/srep00336 · Cited by 795
A Comparative Analysis of Community Detection Algorithms on Artificial Networks
Yang, Z., Algesheimer, R., & Tessone, C. J. (2016) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-127494 · Cited by 685
Political Polarization on Twitter
Conover, M., Ratkiewicz, J., Francisco, M., Goncalves, B., Menczer, F., & Flammini, A. (2021) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v5i1.14126 · Cited by 992
“Label propagation (Raghavan, Albert, and Kumara 2007) works by assigning an initial arbitrary cluster membership to each node and then iteratively updating each node's label according to the label that is shared by most of its neighbors.”
BackgroundCommunity detection in Social Media: Performance and application considerations
Papadopoulos, S., Kompatsiaris, Y., Vakali, A., & Spyridonos, P. (2012) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-011-0224-z · Cited by 615
Boldi, P., Rosa, M., Santini, M., & Vigna, S. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963488 · Cited by 592
Predicting the Political Alignment of Twitter Users
Conover, M. D., Goncalves, B., Ratkiewicz, J., Flammini, A., & Menczer, F. (2011) · 2011 IEEE Third Int'l Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third Int'l Conference on Social Computing · doi:10.1109/passat/socialcom.2011.34 · Cited by 588
A Comparative Analysis of Community Detection Algorithms on Artificial Networks
Yang, Z., Algesheimer, R., & Tessone, C. J. (2016) · Scientific Reports · doi:10.1038/srep30750 · Cited by 578
Community-based greedy algorithm for mining top-K influential nodes in mobile social networks
Wang, Y., Cong, G., Song, G., & Xie, K. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835935 · Cited by 541
Xie, J., Szymanski, B. K., & Liu, X. (2011) · 2011 IEEE 11th International Conference on Data Mining Workshops · doi:10.1109/icdmw.2011.154 · Cited by 519
Community detection in networks: A multidisciplinary review
Javed, M. A., Younis, M. S., Latif, S., Qadir, J., & Baig, A. (2018) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2018.02.011 · Cited by 499
Recent Advances in Graph Partitioning
Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., & Schulz, C. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-49487-6_4 · Cited by 482
The internet of things for smart manufacturing: A review
Yang, H., Kumara, S., Bukkapatnam, S. T. S., & Tsung, F. (2019) · IISE Transactions · doi:10.1080/24725854.2018.1555383 · Cited by 449
Self-citationPolarization 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
Complex Networks: Principles, Methods and Applications
Latora, V., Nicosia, V., & Russo, G. (2017) · Cambridge University Press eBooks · doi:10.1017/9781316216002 · Cited by 372
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
Badawy, A., Ferrara, E., & Lerman, K. (2018) · 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2018.8508646 · 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
Narrow scope for resolution-limit-free community detection
Traag, V. A., Van Dooren, P., & Nesterov, Y. (2011) · Physical Review E · doi:10.1103/physreve.84.016114 · Cited by 353
Community detection in social networks
Bedi, P., & Sharma, C. (2016) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1178 · Cited by 346
Kovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
Evolutionary Network Analysis: A Survey
Aggarwal, C., & Subbian, K. (2014) · ACM Computing Surveys · doi:10.1145/2601412 · Cited by 313
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
Local search of communities in large graphs
Cui, W., Xiao, Y., Wang, H., & Wang, W. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2612179 · Cited by 299
McCune, R. R., Weninger, T., & Madey, G. (2015) · ACM Computing Surveys · doi:10.1145/2818185 · Cited by 294
(2012) · Cited by 289
Towards real-time community detection in large networks
Leung, I. X. Y., Hui, P., Liò, P., & Crowcroft, J. (2009) · Physical Review E · doi:10.1103/physreve.79.066107 · Cited by 289
Towards Linear Time Overlapping Community Detection in Social Networks
Xie, J., & Szymanski, B. K. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-30220-6_3 · Cited by 280
GLay: community structure analysis of biological networks
Su, G., Kuchinsky, A., Morris, J. H., States, D. J., & Meng, F. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq596 · Cited by 275
Networked discontent: The anatomy of protest campaigns in social media
González-Bailón, S., & Wang, N. (2016) · Social Networks · doi:10.1016/j.socnet.2015.07.003 · Cited by 274
Influence-Based Community Partition With Sandwich Method for Social Networks
Ni, Q., Guo, J., Wu, W., & Wang, H. (2023) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2022.3148411 · Cited by 265
Social Features of Online Networks: The Strength of Intermediary Ties in Online Social Media
Grabowicz, P. A., Ramasco, J. J., Moro, E., Pujol, J. M., & Eguiluz, V. M. (2012) · PLoS ONE · doi:10.1371/journal.pone.0029358 · Cited by 263
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
Partisan asymmetries in online political activity
Conover, M. D., Gonçalves, B., Flammini, A., & Menczer, F. (2012) · EPJ Data Science · doi:10.1140/epjds6 · Cited by 234
“In brief, we used Rhaghavan’s label propagation method seeded with node labels determined by Newman’s leading eigenvector modularity maximization method to assign cluster membership to each node (Newman, 2006; Raghavan et al., 2007).”
MethodMapping social dynamics on Facebook: The Brexit debate
Del Vicario, M., Zollo, F., Caldarelli, G., Scala, A., & Quattrociocchi, W. (2017) · Social Networks · doi:10.1016/j.socnet.2017.02.002 · Cited by 233
Finding and characterizing communities in multidimensional networks
Berlingerio, M., Coscia, M., & Giannotti, F. (2011) · 2011 International Conference on Advances in Social Networks Analysis and Mining · doi:10.1109/asonam.2011.104 · Cited by 122
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
“For sparse count matrices (such as those used for structural brain connections), Label Propagation (Raghavan et al., 2007), and Walktrap perform equally well under varied conditions.”
BackgroundMethodWho Falls for Online Political Manipulation?
Badawy, A., Lerman, K., & Ferrara, E. (2019) · Companion Proceedings of The 2019 World Wide Web Conference · doi:10.1145/3308560.3316494 · Cited by 105
“The algorithm proceeds updating labels iteratively and stops when the labels no longer change (see [Raghavan et al. 2007] for more information).”
MethodSocial media behavior is associated with vaccine hesitancy
Rathje, S., He, J. K., Roozenbeek, J., Van Bavel, J. J., & van der Linden, S. (2022) · PNAS Nexus · doi:10.1093/pnasnexus/pgac207 · Cited by 100
Gaiteri, C., Chen, M., Szymanski, B., Kuzmin, K., Xie, J., Lee, C., Blanche, T., Chaibub Neto, E., Huang, S.-C., Grabowski, T., et al. (2015) · Scientific Reports · doi:10.1038/srep16361 · Cited by 76
“ALHC, w/ true # of tier-2 clusters (23) 0.”
BackgroundInfluentialBruno, M., Lambiotte, R., & Saracco, F. (2022) · EPJ Data Science · doi:10.1140/epjds/s13688-022-00330-0 · Cited by 40
Liu, H., Li, P., Zhu, M., Wang, X., Lu, J., & Yu, T. (2016) · PLOS ONE · doi:10.1371/journal.pone.0158247 · Cited by 17
Artificial 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
Metadata
- Authors
- Raghavan, U. N., Albert, R., & Kumara, S.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2007-09-11
- Volume
- 76
- Issue
- 3
- Pages
- 036106-036106
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W2132202037
- Cited by
- 3,502
- References
- 32
- FWCI
- 16.55
- Type
- journal article
- Language
- en
- Open access
- bronze
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.