Parallel Graph Partitioning for Complex Networks
Parallel Graph Partitioning for Complex Networks
复制标题
复杂网络的并行图分区
DOI：
10.1109/tpds.2017.2671868
复制
发表时间：
--
影响因子：
5.3
通讯作者：
Christian Schulz
中科院分区：
文献类型：
--
作者：
Henning Meyerhenke;Peter Sanders;Christian Schulz
处理大型复杂网络，如社交网络或Web图，引起了人们的极大兴趣。要并行执行此操作，我们需要将它们分割成大小大致相等的部分。遗憾的是，以前的并行图分割器最初是为更规则的网状网络开发的，但对于复杂网络并不能很好地工作。在这里，我们通过并行化和适应最初为图聚类开发的标签传播技术来解决这个问题。通过引入尺寸约束，标签传播变得既适用于多级图划分的粗化阶段，也适用于图划分的精化阶段。通过这种方式，我们利用了许多复杂网络中存在的分层簇结构。通过将高度并行的进化算法应用于最粗图，我们获得了非常高的质量。由此产生的系统比ParMetis或PT-Scotch等最先进的系统更具可扩展性，并实现了更高的质量。对于大型复杂网络，性能差异非常大。例如，我们的算法使用高性能集群的512个核心在16秒内对具有3.3G边的Web图进行分区，同时生成高质量的分区--没有一个竞争系统可以在我们的系统上处理这个图。
Processing large complex networks like social networks or web graphs has attracted considerable interest. To do this in parallel, we need to partition them into pieces of roughly equal size. Unfortunately, previous parallel graph partitioners originally developed for more regular mesh-like networks do not work well for complex networks. Here we address this problem by parallelizing and adapting the label propagation technique originally developed for graph clustering. By introducing size constraints, label propagation becomes applicable for both the coarsening and the refinement phase of multilevel graph partitioning. This way we exploit the hierarchical cluster structure present in many complex networks. We obtain very high quality by applying a highly parallel evolutionary algorithm to the coarsest graph. The resulting system is both more scalable and achieves higher quality than state-of-theart systems like ParMetis or PT-Scotch. For large complex networks the performance differences are very big. As an example, our algorithm partitions a web graph with 3.3 G edges in 16 seconds using 512 cores of a high-performance cluster while producing a high quality partition-none of the competing systems can handle this graph on our system.
登录
查看更多内容
DOI：
10.1137/1.9781611972924.2
发表时间：
2011
期刊：
ArXiv
影响因子：
--
作者：
P. Sanders;Christian Schulz
通讯作者：
Christian Schulz
MPI 并行自适应数值模拟的形状优化负载平衡
DOI：
--
发表时间：
2012
期刊：
Graph Partitioning and Graph Clustering
影响因子：
--
作者：
Henning Meyerhenke
通讯作者：
Henning Meyerhenke
DOI：
--
发表时间：
2000
期刊：
影响因子：
--
作者：
R. Engelen
通讯作者：
R. Engelen
通过代数多重网格加速并行 FEM 模拟的形状优化负载平衡
DOI：
--
发表时间：
2006
期刊：
Proceedings 20th IEEE International Parallel & Distributed Processing Symposium
影响因子：
--
作者：
Henning Meyerhenke;B. Monien;Stefan Schamberger
通讯作者：
Stefan Schamberger
影响因子：
1.4
作者：
B. Monien;R. Preis;Ralf Diekmann
通讯作者：
Ralf Diekmann