{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T11:22:36Z","timestamp":1763810556815,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,4,9]],"date-time":"2021-04-09T00:00:00Z","timestamp":1617926400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,9]],"date-time":"2021-04-09T00:00:00Z","timestamp":1617926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Projekt DEAL"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Markov clustering is an effective unsupervised pattern recognition algorithm for data clustering in high-dimensional feature space. However, its community detection performance in complex networks has been demonstrating results far from the state of the art methods such as Infomap and Louvain. The crucial issue is to convert the unweighted network topology in a \u2018smart-enough\u2019 pre-weighted connectivity that adequately steers the stochastic flow procedure behind Markov clustering. Here we introduce a conceptual innovation and we discuss how to leverage network latent geometry notions in order to design similarity measures for pre-weighting the adjacency matrix used in Markov clustering community detection. Our results demonstrate that the proposed strategy improves Markov clustering significantly, to the extent that it is often close to the performance of current state of the art methods for community detection. These findings emerge considering both synthetic \u2018realistic\u2019 networks (with known ground-truth communities) and real networks (with community metadata), and even when the real network connectivity is corrupted by noise artificially induced by missing or spurious links. Our study enhances the generalized understanding of how network geometry plays a fundamental role in the design of algorithms based on network navigability.<\/jats:p>","DOI":"10.1007\/s41109-021-00370-x","type":"journal-article","created":{"date-parts":[[2021,4,9]],"date-time":"2021-04-09T21:02:20Z","timestamp":1618002140000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Geometrical inspired pre-weighting enhances Markov clustering community detection in complex networks"],"prefix":"10.1007","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9447-7130","authenticated-orcid":false,"given":"Claudio","family":"Dur\u00e1n","sequence":"first","affiliation":[]},{"given":"Alessandro","family":"Muscoloni","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0100-8410","authenticated-orcid":false,"given":"Carlo Vittorio","family":"Cannistraci","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,9]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Adamic LA, Glance N (2005) The political blogosphere and the 2004 U.S. Election: divided they blog. LinkKDD 2005, pp 36\u201343","key":"370_CR1","DOI":"10.1145\/1134271.1134277"},{"doi-asserted-by":"publisher","unstructured":"Athanassopoulos S, Kaklamanis C, Laftsidis I, Papaioannou E (2010) An experimental study of greedy routing algorithms. In: Proceedings of International Conference on High Performance Computing & Simulation, pp 150\u2013156. https:\/\/doi.org\/10.1109\/HPCS.2010.5547143","key":"370_CR2","DOI":"10.1109\/HPCS.2010.5547143"},{"key":"370_CR3","doi-asserted-by":"publisher","first-page":"10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"VD Blondel","year":"2008","unstructured":"Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008:10008. https:\/\/doi.org\/10.1088\/1742-5468\/2008\/10\/P10008","journal-title":"J Stat Mech Theory Exp"},{"key":"370_CR4","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1038\/nphys1130","volume":"5","author":"M Bogu\u00f1\u00e1","year":"2008","unstructured":"Bogu\u00f1\u00e1 M, Krioukov D, Claffy KC (2008) Navigability of complex networks. Nat Phys 5:74\u201380. https:\/\/doi.org\/10.1038\/nphys1130","journal-title":"Nat Phys"},{"unstructured":"Cannistraci CV, Muscoloni A (2018) Latent geometry inspired graph dissimilarities enhance affinity propagation community detection in complex networks. 20:063022. ArXiv: 180404566","key":"370_CR5"},{"key":"370_CR6","doi-asserted-by":"publisher","first-page":"i531","DOI":"10.1093\/bioinformatics\/btq376","volume":"26","author":"CV Cannistraci","year":"2010","unstructured":"Cannistraci CV, Ravasi T, Montevecchi FM, Ideker T, Alessio M (2010) Nonlinear dimension reduction and clustering by Minimum Curvilinearity unfold neuropathic pain and tissue embryological classes. Bioinformatics 26:i531\u2013i539","journal-title":"Bioinformatics"},{"key":"370_CR7","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1093\/bioinformatics\/btt208","volume":"29","author":"CV Cannistraci","year":"2013","unstructured":"Cannistraci CV, Alanis-Lobato G, Ravasi T (2013) Minimum curvilinearity to enhance topological prediction of protein interactions by network embedding. Bioinformatics 29:199\u2013209. https:\/\/doi.org\/10.1093\/bioinformatics\/btt208","journal-title":"Bioinformatics"},{"key":"370_CR8","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1214\/13-AOAS710","volume":"51","author":"A Clauset","year":"2009","unstructured":"Clauset A, Rohilla Shalizi C, Newman MEJ (2009) Power-law distributions in empirical data. SIAM Rev 51:661\u2013703. https:\/\/doi.org\/10.1214\/13-AOAS710","journal-title":"SIAM Rev"},{"key":"370_CR9","volume-title":"The hidden power of social networks","author":"R Cross","year":"2004","unstructured":"Cross R, Parker A (2004) The hidden power of social networks. Harvard Business School Press, Brighton"},{"unstructured":"Cs\u00e1rdi G, Nepusz T (2006) The igraph software package for complex network research. Int J Complex Syst. p 1695","key":"370_CR10"},{"key":"370_CR11","first-page":"1","volume":"P09008","author":"L Danon","year":"2005","unstructured":"Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech Theory Exp P09008:1\u201310","journal-title":"J Stat Mech Theory Exp"},{"key":"370_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2016.09.002","volume":"659","author":"S Fortunato","year":"2016","unstructured":"Fortunato S, Hric D (2016) Community detection in networks: a user guide. Phys Rep 659:1\u201344. https:\/\/doi.org\/10.1016\/j.physrep.2016.09.002","journal-title":"Phys Rep"},{"key":"370_CR13","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan M, Newman MEJ (2002) Community structure in social and biological networks. PNAS 99:7821\u20137826. https:\/\/doi.org\/10.1073\/pnas.122653799","journal-title":"PNAS"},{"key":"370_CR14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.062805","author":"D Hric","year":"2014","unstructured":"Hric D, Darst RK, Fortunato S (2014) Community detection in networks: structural communities versus ground truth. Phys Rev E Stat Nonlinear Soft Matter Phys. https:\/\/doi.org\/10.1103\/PhysRevE.90.062805","journal-title":"Phys Rev E Stat Nonlinear Soft Matter Phys"},{"key":"370_CR15","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1093\/comnet\/cnx019","volume":"5","author":"M Jalili","year":"2017","unstructured":"Jalili M, Perc M (2017) Information cascades in complex networks. J Complex Netw 5:665\u2013693. https:\/\/doi.org\/10.1093\/comnet\/cnx019","journal-title":"J Complex Netw"},{"doi-asserted-by":"publisher","unstructured":"Jia G, Cai Z, Musolesi M, Wang Y, Tennant DA, Weber RJM, Heath JK, He S (2012) Community detection in social and biological networks using differential evolution, pp 71\u201385. https:\/\/doi.org\/10.1007\/978-3-642-34413-8_6","key":"370_CR16","DOI":"10.1007\/978-3-642-34413-8_6"},{"key":"370_CR17","doi-asserted-by":"publisher","first-page":"036106","DOI":"10.1103\/PhysRevE.82.036106","volume":"82","author":"D Krioukov","year":"2010","unstructured":"Krioukov D, Papadopoulos F, Kitsak M, Vahdat A, Bogu\u00f1\u00e1 M (2010) Hyperbolic geometry of complex networks. Phys Rev E Stat Nonlinear Soft Matter Phys 82:036106. https:\/\/doi.org\/10.1103\/PhysRevE.82.036106","journal-title":"Phys Rev E Stat Nonlinear Soft Matter Phys"},{"key":"370_CR18","doi-asserted-by":"publisher","first-page":"056117","DOI":"10.1103\/PhysRevE.80.056117","volume":"80","author":"A Lancichinetti","year":"2009","unstructured":"Lancichinetti A, Fortunato S (2009) Community detection algorithms: a comparative analysis. Phys Rev E 80:056117. https:\/\/doi.org\/10.1103\/PhysRevE.80.056117","journal-title":"Phys Rev E"},{"unstructured":"Muscoloni A, Cannistraci CV (2018a) Minimum curvilinear automata with similarity attachment for network embedding and link prediction in the hyperbolic space. ArXiv: 180201183","key":"370_CR21"},{"key":"370_CR20","doi-asserted-by":"publisher","first-page":"052002","DOI":"10.1088\/1367-2630\/aac06f","volume":"20","author":"A Muscoloni","year":"2018","unstructured":"Muscoloni A, Cannistraci CV (2018b) A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities. New J Phys 20:052002. https:\/\/doi.org\/10.1088\/1367-2630\/aac06f","journal-title":"New J Phys"},{"key":"370_CR19","doi-asserted-by":"publisher","first-page":"063022","DOI":"10.1088\/1367-2630\/aac06f","volume":"20","author":"A Muscoloni","year":"2018","unstructured":"Muscoloni A, Cannistraci CV (2018c) Leveraging the nonuniform PSO network model as a benchmark for performance evaluation in community detection and link prediction. New J Phys 20:063022","journal-title":"New J Phys"},{"key":"370_CR22","doi-asserted-by":"publisher","first-page":"1468","DOI":"10.1073\/pnas.1817880116","volume":"116","author":"A Muscoloni","year":"2019","unstructured":"Muscoloni A, Cannistraci CV (2019) Navigability evaluation of complex networks by greedy routing efficiency. Proc Natl Acad Sci 116:1468\u20131469. https:\/\/doi.org\/10.1073\/pnas.1817880116","journal-title":"Proc Natl Acad Sci"},{"key":"370_CR23","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1038\/s41467-017-01825-5","volume":"8","author":"A Muscoloni","year":"2017","unstructured":"Muscoloni A, Thomas JM, Ciucci S, Bianconi G, Cannistraci CV (2017) Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nat Commun 8:1615","journal-title":"Nat Commun"},{"doi-asserted-by":"crossref","unstructured":"Orman GK, Labatut V (2009) A comparison of community detection algorithms on artificial networks. In: Discovery science, pp 242\u2013256","key":"370_CR24","DOI":"10.1007\/978-3-642-04747-3_20"},{"key":"370_CR25","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s10618-011-0224-z","volume":"24","author":"S Papadopoulos","year":"2012","unstructured":"Papadopoulos S, Kompatsiaris Y, Vakali A, Spyridonos P (2012a) Community detection in social media performance and application considerations. Data Min Knowl Discov 24:515\u2013554. https:\/\/doi.org\/10.1007\/s10618-011-0224-z","journal-title":"Data Min Knowl Discov"},{"key":"370_CR26","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1038\/nature11459","volume":"489","author":"F Papadopoulos","year":"2012","unstructured":"Papadopoulos F, Kitsak M, Serrano MA, Bogu\u00f1\u00e1 M, Krioukov D (2012b) Popularity versus similarity in growing networks. Nature 489:537\u2013540. https:\/\/doi.org\/10.1038\/nature11459","journal-title":"Nature"},{"key":"370_CR27","doi-asserted-by":"publisher","first-page":"e18209","DOI":"10.1371\/journal.pone.0018209","volume":"6","author":"M Rosvall","year":"2011","unstructured":"Rosvall M, Bergstrom CT (2011) Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. PLoS ONE 6:e18209. https:\/\/doi.org\/10.1371\/journal.pone.0018209","journal-title":"PLoS ONE"},{"doi-asserted-by":"publisher","unstructured":"Satuluri V, Parthasarathy S (2009) Scalable graph clustering using stochastic flows. In: Proceedings of 15th ACM SIGKDD international conference on knowledge discovery data mining\u2014KDD \u201909, p 737. https:\/\/doi.org\/10.1145\/1557019.1557101","key":"370_CR28","DOI":"10.1145\/1557019.1557101"},{"key":"370_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1103\/PhysRevLett.100.078701","volume":"100","author":"M\u00c1 Serrano","year":"2008","unstructured":"Serrano M\u00c1, Krioukov D, Bogu\u00f1\u00e1 M (2008) Self-similarity of complex networks and hidden metric spaces. Phys Rev Lett 100:1\u20134. https:\/\/doi.org\/10.1103\/PhysRevLett.100.078701","journal-title":"Phys Rev Lett"},{"doi-asserted-by":"publisher","unstructured":"van Dongen S (2000) Graph clustering by flow simulation. Graph Stimul by flow Clust.  https:\/\/doi.org\/10.1016\/j.cosrev.2007.05.001","key":"370_CR49","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"370_CR30","first-page":"2837","volume":"11","author":"NX Vinh","year":"2010","unstructured":"Vinh NX, Epps J, Bailey J (2010) Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance. J Mach Learn Res 11:2837\u20132854","journal-title":"J Mach Learn Res"},{"key":"370_CR31","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1186\/1471-2105-10-99","volume":"10","author":"J Vlasblom","year":"2009","unstructured":"Vlasblom J, Wodak SJ (2009) Markov clustering versus affinity propagation for the partitioning of protein interaction graphs. BMC Bioinform 10:99. https:\/\/doi.org\/10.1186\/1471-2105-10-99","journal-title":"BMC Bioinform"},{"key":"370_CR32","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts DJ, Strogatz SH (1998) Collective dynamics of \u2018small-world\u2019 networks. Nature 393:440\u2013442. https:\/\/doi.org\/10.1038\/30918","journal-title":"Nature"},{"key":"370_CR33","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1109\/NSW.2013.6609210","volume":"2013","author":"J Xie","year":"2013","unstructured":"Xie J, Szymanski BBK (2013) Labelrank: a stabilized label propagation algorithm for community detection in networks. Netw Sci Work: NSW 2013:138\u2013143. https:\/\/doi.org\/10.1109\/NSW.2013.6609210","journal-title":"Netw Sci Work: NSW"},{"key":"370_CR34","doi-asserted-by":"publisher","first-page":"30750","DOI":"10.1038\/srep30750","volume":"6","author":"Z Yang","year":"2016","unstructured":"Yang Z, Algesheimer R, Tessone CJ (2016) A comparative analysis of community detection algorithms on artificial networks. Sci Rep 6:30750. https:\/\/doi.org\/10.1038\/srep30750","journal-title":"Sci Rep"},{"key":"370_CR35","doi-asserted-by":"publisher","first-page":"452","DOI":"10.2307\/3629752","volume":"33","author":"WW Zachary","year":"1977","unstructured":"Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33:452\u2013473. https:\/\/doi.org\/10.2307\/3629752","journal-title":"J Anthropol Res"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00370-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-021-00370-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00370-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,9]],"date-time":"2021-11-09T17:00:49Z","timestamp":1636477249000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-021-00370-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,9]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["370"],"URL":"https:\/\/doi.org\/10.1007\/s41109-021-00370-x","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2021,4,9]]},"assertion":[{"value":"13 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The funding note was missing in the original publication. The article has been updated to rectify the error.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing financial interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"MATLAB code has been used for all the simulations, carried out in a workstation under Windows 8.1 Pro with 512\u00a0GB of RAM and 2 Intel(R) Xenon(R) CPU E5-2687\u00a0W v3 processors with 3.10\u00a0GHz.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Hardware and software"}}],"article-number":"29"}}