论文标题
计算未加权网络的均衡跨越树木
Computing well-balanced spanning trees of unweighted networks
论文作者
论文摘要
网络或图形的生成树是一个子图，该子图将所有节点与边缘数量最少或重量的重量连接起来。生成树是用于简化网络简化和采样的最直接技术之一，也是发现其骨干或骨骼的技术之一。 Prim的算法和Kruskal的算法是计算加权网络的生成树的众所周知的算法，因此也是最受欢迎的网络库中未加权网络的默认过程。在本文中，我们从经验上研究了这些算法在未加权网络上的性能，并将它们与不同的优先级搜索算法进行比较。我们表明，基于广度优先的搜索，更简单的算法可以更好地保留网络的结构，例如节点之间的距离。按经典图指数衡量，生成树也是最紧凑且平衡的。我们通过在合成图和一千多个真实网络上进行实验来支持我们的发现，并展示了计算出的跨越树的实际应用。我们得出的结论是，如果要维护未加权网络的结构，则广度优先的搜索算法应该是首选的选择，并且应该在网络库中实现。
A spanning tree of a network or graph is a subgraph that connects all nodes with the least number or weight of edges. The spanning tree is one of the most straightforward techniques for network simplification and sampling, and for discovering its backbone or skeleton. Prim's algorithm and Kruskal's algorithm are well-known algorithms for computing a spanning tree of a weighted network, and are therefore also the default procedure for unweighted networks in the most popular network libraries. In this paper, we empirically study the performance of these algorithms on unweighted networks and compare them with different priority-first search algorithms. We show that the structure of a network, such as the distances between the nodes, is better preserved by a simpler algorithm based on breadth-first search. The spanning trees are also most compact and well-balanced as measured by classical graph indices. We support our findings with experiments on synthetic graphs and more than a thousand real networks, and demonstrate practical applications of the computed spanning trees. We conclude that if a spanning tree is to maintain the structure of an unweighted network, the breadth-first search algorithm should be the preferred choice, and it should be implemented as such in network libraries.
