The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
Computing Communities in Large Networks Using Random Walks
Open accessAbstract
Dense subgraphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Computing them however is generally expensive. We propose here a measure of similarities between vertices based on random walks which has several important advantages: it captures well the community structure in a network, it can be computed efficiently, it works at various scales, and it can be used in an agglomerative algorithm to compute efficiently the community structure of a network. We propose such an algorithm which runs in time O(mn 2)andspaceO(n 2)inthe worst case, and in time O(n 2 log n) andspaceO(n 2)inmostreal-world cases (n and m are respectively the number of vertices and edges in the input graph). 1
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
Hierarchical Grouping to Optimize an Objective Function
Ward, J. H. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500845 · Cited by 20,598
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
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
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
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
An 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
Hierarchical Organization of Modularity in Metabolic Networks
Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barabási, A.-L. (2002) · Science · doi:10.1126/science.1073374 · Cited by 4,224
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
Network analysis of multivariate data in psychological science
Borsboom, D., Deserno, M. K., Rhemtulla, M., Epskamp, S., Fried, E. I., McNally, R. J., Robinaugh, D. J., Perugini, M., Dalege, J., Costantini, G., et al. (2021) · Nature Reviews Methods Primers · doi:10.1038/s43586-021-00055-w · Cited by 1,371
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
Golino, H. F., & Epskamp, S. (2017) · PLOS ONE · doi:10.1371/journal.pone.0174035 · Cited by 1,060
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
Berthelot, C., Brunet, F., Chalopin, D., Juanchich, A., Bernard, M., Noël, B., Bento, P., Da Silva, C., Labadie, K., Alberti, A., et al. (2014) · Nature Communications · doi:10.1038/ncomms4657 · Cited by 959
Graph clustering based on structural/attribute similarities
Zhou, Y., Cheng, H., & Yu, J. X. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687709 · Cited by 863
A new method for constructing networks from binary data
van Borkulo, C. D., Borsboom, D., Epskamp, S., Blanken, T. F., Boschloo, L., Schoevers, R. A., & Waldorp, L. J. (2014) · Scientific Reports · doi:10.1038/srep05918 · Cited by 757
Random walks and diffusion on networks
Masuda, N., Porter, M. A., & Lambiotte, R. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.07.007 · Cited by 657
Clustering and community detection in directed networks: A survey
Malliaros, F. D., & Vazirgiannis, M. (2013) · Physics Reports · doi:10.1016/j.physrep.2013.08.002 · Cited by 591
Continuous-Time Dynamic Network Embeddings
Nguyen, G. H., Lee, J. B., Rossi, R. A., Ahmed, N. K., Koh, E., & Kim, S. (2018) · Companion of the The Web Conference 2018 on The Web Conference 2018 - WWW '18 · doi:10.1145/3184558.3191526 · Cited by 538
A method for detecting modules in quantitative bipartite networks
Dormann, C. F., & Strauss, R. (2014) · Methods in Ecology and Evolution · doi:10.1111/2041-210x.12139 · Cited by 533
Golino, H., Shi, D., Christensen, A. P., Garrido, L. E., Nieto, M. D., Sadana, R., Thiyagarajan, J. A., & Martinez-Molina, A. (2020) · Psychological Methods · doi:10.1037/met0000255 · Cited by 532
Stability of graph communities across time scales
Delvenne, J.-C., Yaliraki, S. N., & Barahona, M. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0903215107 · Cited by 475
Community Discovery in Dynamic Networks: A Survey
Rossetti, G., & Cazabet, R. (2019) · ACM Computing Surveys · doi:10.1145/3172867 · Cited by 468
iNAP: An integrated network analysis pipeline for microbiome studies
Feng, K., Peng, X., Zhang, Z., Gu, S., He, Q., Shen, W., Wang, Z., Wang, D., Hu, Q., Li, Y., et al. (2022) · iMeta · doi:10.1002/imt2.13 · Cited by 428
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
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
Lambiotte, R., Delvenne, J.-C., & Barahona, M. (2014) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2015.2391998 · Cited by 398
Uncovering Patterns of Inter-Urban Trip and Spatial Interaction from Social Media Check-In Data
Liu, Y., Sui, Z., Kang, C., & Gao, Y. (2014) · PLoS ONE · doi:10.1371/journal.pone.0086026 · Cited by 393
Community 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
Multiscale Embedded Gene Co-expression Network Analysis
Song, W.-M., & Zhang, B. (2015) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004574 · Cited by 356
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 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
Laplacian Dynamics and Multiscale Modular Structure in Networks
Lambiotte, R., Delvenne, J., & Barahona, M. (2008) · doi:10.48550/arxiv.0812.1770 · Cited by 345
Christensen, A. P., & Golino, H. (2021) · Psych · doi:10.3390/psych3030032 · Cited by 339
Kovács, I. A., Palotai, R., Szalay, M. S., & Csermely, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012528 · Cited by 338
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
The triumphs and limitations of computational methods for scRNA-seq
Kharchenko, P. V. (2021) · Nature Methods · doi:10.1038/s41592-021-01171-x · Cited by 321
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
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
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 323
Christensen, A. P., Golino, H., & Silvia, P. J. (2020) · European Journal of Personality · doi:10.1002/per.2265 · Cited by 288
Prediction of emerging technologies based on analysis of the US patent citation network
Érdi, P., Makovi, K., Somogyvári, Z., Strandburg, K., Tobochnik, J., Volf, P., & Zalányi, L. (2013) · Scientometrics · doi:10.1007/s11192-012-0796-4 · Cited by 273
When guests trust hosts for their words: Host description and trust in sharing economy
Tussyadiah, I. P., & Park, S. (2018) · Tourism Management · doi:10.1016/j.tourman.2018.02.002 · Cited by 264
Rodríguez-Soler, R., Uribe-Toril, J., & De Pablo Valenciano, J. (2020) · Land Use Policy · doi:10.1016/j.landusepol.2020.104787 · Cited by 258
On the equivalency of factor and network loadings
Christensen, A. P., & Golino, H. (2021) · Behavior Research Methods · doi:10.3758/s13428-020-01500-6 · Cited by 253
Mapping 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
Pluralistic Collapse: The “Oil Spill” Model of Mass Opinion Polarization
DellaPosta, D. (2020) · American Sociological Review · doi:10.1177/0003122420922989 · Cited by 250
Knefel, M., Tran, U. S., & Lueger-Schuster, B. (2016) · Journal of Anxiety Disorders · doi:10.1016/j.janxdis.2016.09.002 · Cited by 146
Cyberchondria and its Relationships with Related Constructs: a Network Analysis
Starcevic, V., Baggio, S., Berle, D., Khazaal, Y., & Viswasam, K. (2019) · Psychiatric Quarterly · doi:10.1007/s11126-019-09640-5 · Cited by 135
Trend of Narratives in the Age of Misinformation
Bessi, A., Zollo, F., Del Vicario, M., Scala, A., Caldarelli, G., & Quattrociocchi, W. (2015) · PLOS ONE · doi:10.1371/journal.pone.0134641 · 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
Parsing Heterogeneity in the Brain Connectivity of Depressed and Healthy Adults During Positive Mood
Price, R. B., Lane, S., Gates, K., Kraynak, T. E., Horner, M. S., Thase, M. E., & Siegle, G. J. (2017) · Biological Psychiatry · doi:10.1016/j.biopsych.2016.06.023 · Cited by 106
Data-Driven Subgroups in Depression Derived from Directed Functional Connectivity Paths at Rest
Price, R. B., Gates, K., Kraynak, T. E., Thase, M. E., & Siegle, G. J. (2017) · Neuropsychopharmacology · doi:10.1038/npp.2017.97 · Cited by 98
A network approach to climate change anxiety and its key related features
Heeren, A., Mouguiama-Daouda, C., & McNally, R. J. (2023) · Journal of Anxiety Disorders · doi:10.1016/j.janxdis.2022.102625 · Cited by 88
Czarna, A. Z., Leifeld, P., Śmieja, M., Dufner, M., & Salovey, P. (2016) · Personality and Social Psychology Bulletin · doi:10.1177/0146167216666265 · Cited by 76
A network approach to hypersexuality: insights and clinical implications
Werner, M., Štulhofer, A., Waldorp, L., & Jurin, T. (2018) · The Journal of Sexual Medicine · doi:10.1016/j.jsxm.2018.01.009 · Cited by 58
Maladaptive daydreaming and emotional regulation difficulties: a network analysis
Greene, T., West, M., & Somer, E. (2020) · Psychiatry Research · doi:10.1016/j.psychres.2020.112799 · Cited by 58
Yankouskaya, A., Babiker, A., Rizvi, S., Alshakhsi, S., Liebherr, M., & Ali, R. (2025) · ACM Transactions on the Web · doi:10.1145/3765895 · Cited by 32
A Network Analysis Approach on the Psychological Flexibility/Inflexibility Model
Christodoulou, A., Karekla, M., Costantini, G., & Michaelides, M. P. (2023) · Behavior Therapy · doi:10.1016/j.beth.2023.01.002 · Cited by 22
Metadata
- Authors
- Pons, P., & Latapy, M.
- Venue
- Journal of Graph Algorithms and Applications
- Published
- 2006
- Volume
- 10
- Issue
- 2
- Pages
- 191-218
- ISSN
- 1526-1719 (ISSN-L)
- OpenAlex
- W2033590892
- Cited by
- 1,501
- References
- 21
- FWCI
- 11.35
- Type
- journal article
- Language
- en
- Open access
- diamond
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.