{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T21:11:30Z","timestamp":1762981890475,"version":"3.37.3"},"reference-count":23,"publisher":"IOP Publishing","issue":"3","license":[{"start":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T00:00:00Z","timestamp":1723075200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T00:00:00Z","timestamp":1723075200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/iopscience.iop.org\/info\/page\/text-and-data-mining"}],"funder":[{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","award":["2022.09122.PTDC"],"award-info":[{"award-number":["2022.09122.PTDC"]}]},{"DOI":"10.13039\/100000092","name":"U.S. National Library of Medicine","doi-asserted-by":"crossref","award":["01LM011945-01"],"award-info":[{"award-number":["01LM011945-01"]}],"id":[{"id":"10.13039\/100000092","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["iopscience.iop.org"],"crossmark-restriction":false},"short-container-title":["J. Phys. Complex."],"published-print":{"date-parts":[[2024,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Minimum spanning trees and forests are powerful sparsification techniques that remove cycles from weighted graphs to minimize total edge weight while preserving node reachability, with applications in computer science, network science, and graph theory. Despite their utility and ubiquity, they have several limitations, including that they are only defined for undirected networks, they significantly alter dynamics on networks, and they do not generally preserve important network features such as shortest distances, shortest path distribution, and community structure. In contrast, distance backbones, which are subgraphs formed by all edges that obey a generalized triangle inequality, are well defined in directed and undirected graphs and preserve those and other important network features. The backbone of a graph is defined with respect to a specified path-length operator that aggregates weights along a path to define its length, thereby associating a cost to indirect connections. The backbone is the union of all shortest paths between each pair of nodes according to the specified operator. One such operator, the max function, computes the length of a path as the largest weight of the edges that compose it (a weakest link criterion). It is the only operator that yields an algebraic structure for computing shortest paths that is consistent with De Morgan\u2019s laws. Applying this operator yields the ultrametric backbone of a graph in that (semi-triangular) edges whose weights are larger than the length of an indirect path connecting the same nodes (i.e. those that break the generalized triangle inequality based on max as a path-length operator) are removed. We show that the ultrametric backbone is the union of minimum spanning forests in undirected graphs and provides a new generalization of minimum spanning trees to directed graphs that, unlike minimum equivalent graphs and minimum spanning arborescences, preserves all <jats:inline-formula>\n                     <jats:tex-math\/>\n                     <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" overflow=\"scroll\">\n                        <mml:mrow>\n                           <mml:mo movablelimits=\"true\">max<\/mml:mo>\n                           <mml:mo>\u2212<\/mml:mo>\n                           <mml:mo movablelimits=\"true\">min<\/mml:mo>\n                        <\/mml:mrow>\n                     <\/mml:math>\n                  <\/jats:inline-formula> shortest paths and De Morgan\u2019s law consistency.<\/jats:p>","DOI":"10.1088\/2632-072x\/ad679e","type":"journal-article","created":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T22:53:41Z","timestamp":1721948021000},"page":"035009","update-policy":"https:\/\/doi.org\/10.1088\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The ultrametric backbone is the union of all minimum spanning forests"],"prefix":"10.1088","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4356-9809","authenticated-orcid":true,"given":"Jordan C","family":"Rozum","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9402-887X","authenticated-orcid":true,"given":"Luis M","family":"Rocha","sequence":"additional","affiliation":[]}],"member":"266","published-online":{"date-parts":[[2024,8,8]]},"reference":[{"key":"jpcomplexad679ebib1","first-page":"137","article-title":"Semi-metric behavior in document networks and its application to recommendation systems","author":"Rocha","year":"2003"},{"key":"jpcomplexad679ebib2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.056113","article-title":"Influence of the link weight structure on the shortest path","volume":"71","author":"Van Mieghem","year":"2005","journal-title":"Phys. Rev. E"},{"key":"jpcomplexad679ebib3","doi-asserted-by":"publisher","first-page":"cnab021","DOI":"10.1093\/comnet\/cnab021","article-title":"The distance backbone of complex networks","volume":"9","author":"Simas","year":"2021","journal-title":"J. Complex Netw."},{"key":"jpcomplexad679ebib4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pcbi.1010854","article-title":"Contact networks have small metric backbones that maintain community structure and are primary transmission subgraphs","volume":"19","author":"Brattig Correia","year":"2023","journal-title":"PLOS Comput. Biol."},{"key":"jpcomplexad679ebib5","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.056138","article-title":"Phase transition in the link weight structure of networks","volume":"72","author":"Van Mieghem","year":"2005","journal-title":"Phys. Rev. E"},{"key":"jpcomplexad679ebib6","first-page":"13","article-title":"Resistance distance, information centrality, node vulnerability and vibrations in complex networks","author":"Estrada","year":"2010"},{"key":"jpcomplexad679ebib7","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1016\/j.chaos.2018.09.044","article-title":"Tuned communicability metrics in networks. The case of alternative routes for urban traffic","volume":"116","author":"Silver","year":"2018","journal-title":"Chaos Solitons Fractals"},{"key":"jpcomplexad679ebib8","first-page":"227","article-title":"Distance closures on complex networks","volume":"vol 3","author":"Simas","year":"2015"},{"key":"jpcomplexad679ebib9","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1073\/pnas.28.12.535","article-title":"Statistical metrics","volume":"28","author":"Menger","year":"1942","journal-title":"PNAS"},{"year":"1995","author":"Klir","key":"jpcomplexad679ebib10"},{"key":"jpcomplexad679ebib11","first-page":"135","article-title":"The distance backbone of directed networks","volume":"vol 1078","author":"Xavier Costa","year":"2023"},{"article-title":"Stochastic models and transitivity in complex networks","year":"2012","author":"Simas","key":"jpcomplexad679ebib12"},{"key":"jpcomplexad679ebib13","doi-asserted-by":"publisher","first-page":"140","DOI":"10.3389\/fncom.2015.00140","article-title":"A winding road: Alzheimer\u2019s disease increases circuitous functional connectivity pathways","volume":"9","author":"Suckling","year":"2015","journal-title":"Frontiers Comput. Neurosci."},{"key":"jpcomplexad679ebib14","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0136388","article-title":"Semi-metric topology of the human connectome: sensitivity and specificity to autism and major depressive disorder","volume":"10","author":"Simas","year":"2015","journal-title":"PLoS One"},{"key":"jpcomplexad679ebib15","doi-asserted-by":"publisher","DOI":"10.1101\/2022.03.02.482557","article-title":"The conserved transcriptional program of metazoan male germ cells uncovers ancient origins of human infertility","author":"Brattig Correia","year":"2022","journal-title":"bioRxiv Preprint"},{"key":"jpcomplexad679ebib16","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1109\/TNET.2008.925089","article-title":"The observable part of a network","volume":"17","author":"Van Mieghem","year":"2009","journal-title":"IEEE\/ACM Trans. Netw."},{"article-title":"Semi-metric topology characterizes epidemic spreading on complex networks","year":"2023","author":"Soriano Pa\u00f1os","key":"jpcomplexad679ebib17"},{"key":"jpcomplexad679ebib18","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","article-title":"The transitive reduction of a directed graph","volume":"1","author":"Aho","year":"1972","journal-title":"SIAM J. Comput."},{"key":"jpcomplexad679ebib19","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321864.321866","article-title":"An algorithm for finding a minimal equivalent graph of a digraph","volume":"22","author":"Hsu","year":"1975","journal-title":"J. ACM"},{"key":"jpcomplexad679ebib20","doi-asserted-by":"publisher","first-page":"2924","DOI":"10.1016\/j.dam.2007.12.003","article-title":"The minimum spanning strong subdigraph problem is fixed parameter tractable","volume":"156","author":"Bang-Jensen","year":"2008","journal-title":"Discrete Appl. Math."},{"key":"jpcomplexad679ebib21","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/0020-0190(78)90030-3","article-title":"The min-max spanning tree problem and some extensions","volume":"7","author":"Camerini","year":"1978","journal-title":"Inf. Process. Lett."},{"key":"jpcomplexad679ebib22","first-page":"133","article-title":"Spanning trees and arborescences","author":"Korte","year":"2018"},{"key":"jpcomplexad679ebib23","doi-asserted-by":"publisher","first-page":"48","DOI":"10.2307\/2033241","article-title":"On the shortest spanning subtree of a graph and the traveling salesman problem","volume":"vol 7","author":"Joseph","year":"1956"}],"container-title":["Journal of Physics: Complexity"],"original-title":[],"link":[{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-072X\/ad679e","content-type":"text\/html","content-version":"am","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-072X\/ad679e\/pdf","content-type":"application\/pdf","content-version":"am","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-072X\/ad679e","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-072X\/ad679e\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-072X\/ad679e\/pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-072X\/ad679e\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-072X\/ad679e\/pdf","content-type":"application\/pdf","content-version":"am","intended-application":"similarity-checking"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-072X\/ad679e\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T09:13:48Z","timestamp":1723108428000},"score":1,"resource":{"primary":{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-072X\/ad679e"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,8]]},"references-count":23,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2024,8,8]]},"published-print":{"date-parts":[[2024,9,1]]}},"URL":"https:\/\/doi.org\/10.1088\/2632-072x\/ad679e","relation":{},"ISSN":["2632-072X"],"issn-type":[{"type":"electronic","value":"2632-072X"}],"subject":[],"published":{"date-parts":[[2024,8,8]]},"assertion":[{"value":"The ultrametric backbone is the union of all minimum spanning forests","name":"article_title","label":"Article Title"},{"value":"Journal of Physics: Complexity","name":"journal_title","label":"Journal Title"},{"value":"paper","name":"article_type","label":"Article Type"},{"value":"\u00a9 2024 The Author(s). Published by IOP Publishing Ltd","name":"copyright_information","label":"Copyright Information"},{"value":"2024-03-19","name":"date_received","label":"Date Received","group":{"name":"publication_dates","label":"Publication dates"}},{"value":"2024-07-25","name":"date_accepted","label":"Date Accepted","group":{"name":"publication_dates","label":"Publication dates"}},{"value":"2024-08-08","name":"date_epub","label":"Online publication date","group":{"name":"publication_dates","label":"Publication dates"}}]}}