Rozum Jordan C, Rocha Luis M
Department of Systems Science and Industrial Engineering, Binghamton University (State University of New York), Binghamton, NY, United States of America.
J Phys Complex. 2024 Sep 1;5(3):035009. doi: 10.1088/2632-072X/ad679e. Epub 2024 Aug 8.
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's 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 shortest paths and De Morgan's law consistency.
最小生成树和森林是强大的稀疏化技术，可从加权图中移除环以在保持节点可达性的同时最小化总边权，在计算机科学、网络科学和图论中都有应用。尽管它们很有用且很常见，但也有一些局限性，包括它们仅针对无向网络定义，会显著改变网络上的动态，并且通常不会保留重要的网络特征，如最短距离、最短路径分布和社区结构。相比之下，距离骨干是由所有服从广义三角不等式的边形成的子图，在有向图和无向图中都有明确的定义，并保留了这些以及其他重要的网络特征。图的骨干是相对于指定的路径长度算子定义的，该算子沿路径聚合权重以定义其长度，从而为间接连接赋予成本。骨干是根据指定算子在每对节点之间的所有最短路径的并集。一种这样的算子，即最大值函数，将路径的长度计算为组成它的边的最大权重（最弱链路准则）。它是唯一能产生与德摩根定律一致的用于计算最短路径的代数结构的算子。应用此算子会产生图的超度量骨干，因为权重大于连接相同节点的间接路径长度的（半三角形）边（即那些基于最大值作为路径长度算子违反广义三角不等式的边）会被移除。我们表明，超度量骨干是无向图中最小生成森林的并集，并为有向图提供了一种新的最小生成树推广，与最小等价图和最小生成树形图不同，它保留了所有最短路径和德摩根定律的一致性。
