{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T21:21:00Z","timestamp":1777929660458,"version":"3.51.4"},"reference-count":51,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2021,12,20]],"date-time":"2021-12-20T00:00:00Z","timestamp":1639958400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Fujitsu Limited and Fujitsu Consulting (Canada) Inc"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,12,20]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this study, we compare distance measures with respect to their ability to capture vertex community structure and the scalability of their computation. Our goal is to find a distance measure which can be used in an aggregate pairwise minimization clustering scheme. The minimization should lead to subsets of vertices with high induced subgraph density. Our definition of distance is rooted in the notion that vertices sharing more connections are closer to each other than vertices which share fewer connections. This definition differs from that of the geodesic distance typically used in graphs. It is based on neighbourhood overlap, not shortest path. We compare four distance measures from the literature and evaluate their accuracy in reflecting intra-cluster density, when aggregated (averaged) at the cluster level. Our tests are conducted on synthetic graphs, where clusters and intra-cluster densities are known in advance. We find that amplified commute, Otsuka\u2013Ochiai and Jaccard distances display a consistent inverse relation to intra-cluster density. We also conclude that the computation of amplified commute distance does not scale as well to large graphs as that of the other two distances.<\/jats:p>","DOI":"10.1093\/comnet\/cnac003","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T20:13:01Z","timestamp":1643055181000},"source":"Crossref","is-referenced-by-count":5,"title":["An empirical comparison of connectivity-based distances on a graph and their computational scalability"],"prefix":"10.1093","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9261-8147","authenticated-orcid":false,"given":"Pierre","family":"Miasnikof","sequence":"first","affiliation":[{"name":"The Edward S. Rogers Sr. Department of Electrical & Computer Engineering, 10 King\u2019s College Road, Toronto, ON, M5S 3G4, Canada and Data Sciences Institute, University of Toronto, 700 University Avenue, 17th Floor, Toronto, ON, M5G 1Z5, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander Y","family":"Shestopaloff","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonidas","family":"Pitsoulis","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, Aristotle University of Thessaloniki, Thessaloniki 54125, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Ponomarenko","sequence":"additional","affiliation":[{"name":"Laboratory of Algorithms and Technologies for Networks Analysis, National Research University Higher School of Economics, 136 Rodionova str., Nizhny Novgorod 603093, Russia and Center for Hydroacoustics and Geophysical Research Division, Institute of Applied Physics of The Russian Academy of Sciences, 46 Ulyanova str., Nizhny Novgorod 603950, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,2,17]]},"reference":[{"key":"2022021706051199100_B1","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10898-009-9520-1","article-title":"Linear and quadratic programming approaches for the general graph partitioning problem","volume":"48","author":"Fan,","year":"2010","journal-title":"J. Global Optim."},{"key":"2022021706051199100_B2","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/978-3-642-17458-2_15","article-title":"Robust optimization of graph partitioning and critical node detection in analyzing networks","volume-title":"Proceedings of the 4th International Conference on Combinatorial Optimization and Applications - Volume Part I","author":"Fan,","year":"2010"},{"key":"2022021706051199100_B3","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2011.10.015","article-title":"Robust optimization of graph partitioning involving interval uncertainty","volume":"447","author":"Fan,","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"2022021706051199100_B4","first-page":"54","article-title":"A QUBO formulation of the k-medoids problem","volume-title":"Proceedings of the Conference on \u201cLernen, Wissen, Daten, Analysen\u201d, Berlin, Germany, September 30 - October 2, 2019","author":"Bauckhage,","year":"2019"},{"key":"2022021706051199100_B5","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato,","year":"2010","journal-title":"Phys. Rep."},{"key":"2022021706051199100_B6","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/978-3-319-49787-7_10","article-title":"Modularity of complex networks models","volume-title":"Algorithms and Models for the Web Graph","author":"Ostroumova Prokhorenkova,","year":"2016"},{"key":"2022021706051199100_B7","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1016\/j.endm.2017.07.058","article-title":"Modularity in several random graph models","volume":"61","author":"Ostroumova Prokhorenkova,","year":"2017","journal-title":"Electron. Notes Discrete Math."},{"key":"2022021706051199100_B8","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Survey: graph clustering","volume":"1","author":"Schaeffer,","year":"2007","journal-title":"Comput. Sci. Rev."},{"key":"2022021706051199100_B9","article-title":"A tutorial on formulating and using QUBO models","author":"Glover,","year":"2018"},{"key":"2022021706051199100_B10","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.dam.2010.11.017","article-title":"A class of graph-geodetic distances generalizing the shortest-path and the resistance distances","volume":"159","author":"Chebotarev,","year":"2011","journal-title":"Discrete Appl. Math."},{"key":"2022021706051199100_B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pone.0255717","article-title":"Overlapping community detection in networks based on link partitioning and partitioning around medoids","volume":"16","author":"Ponomarenko,","year":"2021","journal-title":"PLoS One"},{"key":"2022021706051199100_B12","first-page":"2622","article-title":"Getting lost in space: large sample analysis of the resistance distance","volume-title":"Advances in Neural Information Processing Systems 23","author":"von Luxburg,","year":"2010"},{"key":"2022021706051199100_B13","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-030-65347-7_16","article-title":"Distances on a graph","volume-title":"Complex Networks & Their Applications IX","author":"Miasnikof,","year":"2021"},{"key":"2022021706051199100_B14","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.neunet.2012.03.001","article-title":"An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification","volume":"31","author":"Fouss,","year":"2012","journal-title":"Neural Netw."},{"key":"2022021706051199100_B15","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1016\/j.physa.2013.09.016","article-title":"Developments in the theory of randomized shortest paths with a comparison of graph node distances","volume":"393","author":"Kivimki,","year":"2014","journal-title":"Physica A"},{"key":"2022021706051199100_B16","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/978-3-319-44778-0_23","article-title":"Comparison of graph node distances on clustering tasks","volume-title":"Artificial Neural Networks and Machine Learning \u2013 ICANN 2016","author":"Sommer,","year":"2016"},{"key":"2022021706051199100_B17","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","article-title":"An information flow model for conflict and fission in small groups","volume":"33","author":"Zachary,","year":"1977","journal-title":"J. Anthropol. Res"},{"key":"2022021706051199100_B18","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan,","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2022021706051199100_B19","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/978-3-030-58657-7_31","article-title":"Network distances for weighted digraphs","volume-title":"Mathematical Optimization Theory and Operations Research","author":"Granata,","year":"2020"},{"key":"2022021706051199100_B20","doi-asserted-by":"crossref","DOI":"10.1016\/j.physrep.2016.09.002","article-title":"Community detection in networks: a user guide","author":"Fortunato,","year":"2016"},{"key":"2022021706051199100_B21","doi-asserted-by":"crossref","first-page":"2021","DOI":"10.3390\/jrfm14010034","article-title":"Market graph clustering via Qubo and digital annealing","volume":"14","author":"Hong,","year":"2021","journal-title":"J. Risk Financ. Manag."},{"key":"2022021706051199100_B22","doi-asserted-by":"crossref","DOI":"10.3389\/fphy.2019.00048","article-title":"Physics-inspired optimization for quadratic unconstrained problems using a digital annealer","volume":"7","author":"Aramon,","year":"2019","journal-title":"Front. Phys."},{"key":"2022021706051199100_B23","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1088\/0305-4470\/19\/9\/033","article-title":"Application of statistical mechanics to NP-complete problems in combinatorial optimisation","volume":"19","author":"Fu,","year":"1986","journal-title":"J. Phys. A"},{"key":"2022021706051199100_B24","doi-asserted-by":"crossref","DOI":"10.3389\/fphy.2014.00005","article-title":"Ising formulations of many NP problems","volume":"2","author":"Lucas,","year":"2014","journal-title":"Front. Phys."},{"key":"2022021706051199100_B25","first-page":"121","article-title":"Measures of clustering quality: a working set of axioms for clustering","volume-title":"Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference","author":"Ackerman,","year":"2008"},{"key":"2022021706051199100_B26","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1073\/pnas.0605965104","article-title":"Resolution limit in community detection","volume":"104","author":"Fortunato,","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2022021706051199100_B27","first-page":"046106","article-title":"Performance of modularity maximization in practical contexts","volume":"81","author":"Good,","year":"2010","journal-title":"preprint"},{"key":"2022021706051199100_B28","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1140\/epjb\/e2013-40169-1","article-title":"Bad communities with high modularity","volume":"86","author":"Kehagias,","year":"2013","journal-title":"Eur. Phys. J. B"},{"key":"2022021706051199100_B29","first-page":"170","article-title":"Algorithms and Models for the Web Graph","volume-title":"A Statistical Performance Analysis of Graph Clustering Algorithms","author":"Miasnikof,","year":"2018"},{"key":"2022021706051199100_B30","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnaa012","article-title":"A density-based statistical analysis of graph clustering algorithm performance","volume":"3","author":"Miasnikof,","year":"2020","journal-title":"J. Complex Netw."},{"key":"2022021706051199100_B31","doi-asserted-by":"crossref","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","article-title":"Fast unfolding of communities in large networks","author":"Blondel,","year":"2008","journal-title":"J. Stat. Mech."},{"key":"2022021706051199100_B32","article-title":"Graph clustering with Boltzmann machines","author":"Miasnikof,","year":"2021"},{"key":"2022021706051199100_B33","article-title":"Resistance distance distribution in large sparse random graphs","author":"Akara-pipattana,","year":"2021"},{"key":"2022021706051199100_B34","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.ejc.2018.02.002","article-title":"Similarities on graphs: kernels versus proximity measures","volume":"80","author":"Avrachenkov,","year":"2019","journal-title":"Eur. J. Combin."},{"key":"2022021706051199100_B35","doi-asserted-by":"crossref","first-page":"15879","DOI":"10.1073\/pnas.252631999","article-title":"The average distances in random graphs with given expected degrees","volume":"99","author":"Chung,","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2022021706051199100_B36","article-title":"The matrix-forest theorem and measuring relations in small social groups","author":"Chebotarev,","year":"2006"},{"key":"2022021706051199100_B37","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s11750-020-00563-0","article-title":"Distance geometry and data science","volume":"28","author":"Liberti,","year":"2020","journal-title":"TOP"},{"key":"2022021706051199100_B38","doi-asserted-by":"crossref","first-page":"93","DOI":"10.2307\/2577097","article-title":"Positions in networks*","volume":"55","author":"Burt,","year":"1976","journal-title":"Soc. Forces"},{"key":"2022021706051199100_B39","doi-asserted-by":"crossref","first-page":"522","DOI":"10.2331\/suisan.22.522","article-title":"Zoogeographical studies on the soleoid fishes found in Japan and its neighbouring regions-I","volume":"22","author":"Ochiai,","year":"1957","journal-title":"Nippon Suisan Gakkaishi"},{"key":"2022021706051199100_B40","article-title":"Matrix-forest theorems","author":"Chebotarev,","year":"2006"},{"key":"2022021706051199100_B41","article-title":"The forest metrics for graph vertices","author":"Chebotarev,","year":"2006"},{"key":"2022021706051199100_B42","doi-asserted-by":"crossref","first-page":"2363","DOI":"10.1162\/neco.2009.11-07-643","article-title":"Randomized shortest-path problems: two related models","volume":"21","author":"Marco","year":"2009","journal-title":"Neural Comput."},{"key":"2022021706051199100_B43","first-page":"785","article-title":"A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances","volume-title":"Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201908","author":"Yen,"},{"key":"2022021706051199100_B44","first-page":"036106","article-title":"Hyperbolic geometry of complex networks","volume":"82","author":"Krioukov,","year":"2010"},{"key":"2022021706051199100_B45","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1038\/s42254-020-00264-4","article-title":"Network geometry","volume":"3","author":"Bogu\u00f1\u00e1,","year":"2021","journal-title":"Nat. Rev. Phys."},{"key":"2022021706051199100_B46","doi-asserted-by":"crossref","first-page":"4317","DOI":"10.1016\/j.laa.2012.01.017","article-title":"The communicability distance in graphs","volume":"436","author":"Estrada,","year":"2012","journal-title":"Linear Algebra Appl."},{"key":"2022021706051199100_B47","article-title":"SNAP Datasets: Stanford large network dataset collection","author":"Leskovec,","year":"2014"},{"key":"2022021706051199100_B48","first-page":"547","article-title":"\u00c9tude de la distribution florale dans une portion des Alpes et du Jura","volume":"37","author":"Jaccard,","year":"1901","journal-title":"Bulletin de la Soci\u00e9t\u00e9 Vaudoise des Sciences Naturelles"},{"key":"2022021706051199100_B49","article-title":"The extended Jaccard distance in complex networks","author":"Camby,","year":"2017","journal-title":"Les Cahiers du GERAD"},{"key":"2022021706051199100_B50","first-page":"1751","article-title":"Hitting and commute times in large random neighborhood graphs","volume":"15","author":"von Luxburg,","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"2022021706051199100_B51","first-page":"11","article-title":"Exploring network structure, dynamics, and function using NetworkX","volume-title":"Proceedings of the 7th Python in Science Conference","author":"Hagberg,","year":"2008"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/1\/cnac003\/42542697\/cnac003.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/1\/cnac003\/42542697\/cnac003.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T06:05:47Z","timestamp":1645077947000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnac003\/6529776"}},"subtitle":[],"editor":[{"given":"Ernesto","family":"Estrada","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,12,20]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12,20]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnac003","relation":{},"ISSN":["2051-1310","2051-1329"],"issn-type":[{"value":"2051-1310","type":"print"},{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,2,1]]},"published":{"date-parts":[[2021,12,20]]},"article-number":"cnac003"}}