Tree-Based Coarsening and Partitioning of Complex Networks
Tree-Based Coarsening and Partitioning of Complex Networks
复制标题
复杂网络的基于树的粗化和划分
DOI：
10.1145/2851496
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
C. Schulz
中科院分区：
文献类型：
--
作者：
R. Glantz;H. Meyerhenke;C. Schulz
一个网络的越来越粗糙的版本的层次结构允许人们同时在多个尺度上表示网络。通常，在网络上生成层次结构的基本操作是合并相邻顶点，该操作可以通过收缩两个顶点之间的边来实现。这样的层次结构是通过选择要在一个级别和下一个较粗级别之间收缩的边缘来定义的。该选择可以涉及（i）对边进行评级，（ii）约束选择（例如，所选择的边形成匹配），以及（iii）在约束下最大化所选择的边的总速率。在这篇文章中，我们提出了一种新的边等级划分方法：（i）定义网络边的权值，表示边通过最短路径的连通性的重要性，（ii）根据这些权值计算最小权值生成树，（iii）计算最小权值生成树，（iii）基于树的基本割的电导值对网络边进行评级。为了使我们新的边评级的计算效率高，我们开发了第一个最优线性时间算法来计算给定生成树的所有基本割的电导值。我们将新的边缘评级集成到一个领先的多级图分割器中，并为后者配备了一个新的贪婪后处理，用于优化分区的最大通信量（MCV），我们的实验，在其中我们bipartition经常使用的基准网络，表明后处理减少MCV 11.3%。我们的新边缘评级，这里用于基于匹配的粗化，与之前的最佳评级相比，MCV后处理进一步降低了10.3%。总的来说，在运行时间适度增加的情况下，我们的新方法将复杂网络分区的MCV降低了20.4%。
A hierarchy of increasingly coarse versions of a network allows one to represent the network on multiple scales at the same time. Often, the elementary operation for generating a hierarchy on a network is merging adjacent vertices, an operation that can be realized through contracting the edge between the two vertices. Such a hierarchy is defined by the selection of the edges to be contracted between a level and the next coarser level. The selection may involve (i) rating the edges, (ii) constraining the selection (e.g., that the selected edges form a matching), as well as (iii) maximizing the total rate of the selected edges under the constraints. Hierarchies of this kind are, among others, involved in multilevel methods for partitioning networks—a prerequisite for processing in parallel with distributed memory.In this article, we propose a new edge rating by (i) defining weights for the edges of a network that express the edges’ importance for connectivity via shortest paths, (ii) computing a minimum weight spanning tree with respect to these weights, and (iii) rating the network edges based on the conductance values of the tree’s fundamental cuts.To make the computation of our new edge rating efficient, we develop the first optimal linear-time algorithm to compute the conductance values ofallfundamental cuts of a given spanning tree. We integrate the new edge rating into a leading multilevel graph partitioner and equip the latter also with a new greedy postprocessing for optimizing the Maximum Communication Volume (MCV) of a partition.Our experiments, in which we bipartition frequently used benchmark networks, show that the postprocessing reduces MCV by 11.3%. Our new edge rating, here used for matching-based coarsening, further reduces MCV by 10.3% compared to the previously best rating with MCV postprocessing in place for both ratings. In total, with a modest increase in running time, our new approach reduces the MCV of complex network partitions by 20.4%.
登录
查看更多内容
RMQ 问题的理论和实践改进及其在 LCA 和 LCE 中的应用
DOI：
10.1007/11780441_5
发表时间：
2006
期刊：
Journal of computational biology : a journal of computational molecular cell biology
影响因子：
--
作者：
J. Fischer;Volker Heun
通讯作者：
Volker Heun
通过代数多重网格加速并行 FEM 模拟的形状优化负载平衡
DOI：
--
发表时间：
2006
期刊：
Proceedings 20th IEEE International Parallel & Distributed Processing Symposium
影响因子：
--
作者：
Henning Meyerhenke;B. Monien;Stefan Schamberger
通讯作者：
Stefan Schamberger
n 级图划分
DOI：
10.1007/978-3-642-15775-2_24
发表时间：
2010
期刊：
Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining
影响因子：
--
作者：
Vitaly Osipov;P. Sanders
通讯作者：
P. Sanders
构建双不规则金字塔的等效收缩核
DOI：
--
发表时间：
1996
期刊：
Theoretical Foundations of Computer Vision
影响因子：
--
作者：
W. Kropatsch
通讯作者：
W. Kropatsch
通过循环空间采样快速计算小切口
DOI：
--
发表时间：
2007
期刊：
TALG
影响因子：
--
作者：
David Pritchard;R. Thurimella
通讯作者：
R. Thurimella