Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering
Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering
复制标题
DOI：
10.1007/s10732-016-9315-8
复制
发表时间：
2016-10
影响因子：
2.7
通讯作者：
Henning Meyerhenke;P. Sanders;Christian Schulz
中科院分区：
文献类型：
--
作者：
Henning Meyerhenke;P. Sanders;Christian Schulz
在实践中，最常用的方法来解决图划分问题是多级元启发式。在本文中，我们介绍了大小约束标签传播（SCLaP），并展示了它如何可以用来实例化的粗化阶段和细化阶段的多级图分区。我们主要针对具有高度不规则和层次聚类结构的网络（但也可以划分其他网络类型）。此外，我们增加了几个扩展的基本算法，以进一步提高其速度和/或解决方案的质量。根据使用SCLaP的结果分区器的配置，我们能够计算出优于所有竞争对手的高质量分区，或者相反，计算出与质量方面的最佳竞争对手hMetis类似的好分区，同时速度快一个数量级。我们最快的配置在我们的研究中使用顺序代码在大约10分钟内划分了最大的真实世界图（它有33亿条边），而比最快的竞争对手kMetis减少了不到一半的边。
The most commonly used method to tackle the graph partitioning problem in practice is the multilevel metaheuristic. In this paper we introducesize-constrained label propagation(SCLaP) and show how it can be used to instantiate both the coarsening phase and the refinement phase of multilevel graph partitioning. We mainly target networks with highly irregular and hierarchically clustered structure (but other network types can be partitioned as well). Additionally, we augment the basic algorithm with several extensions to further improve its speed and/or solution quality. Depending on the configuration of the resulting partitioner using SCLaP, we are able to compute high-quality partitions outperforming all competitors, or instead, to compute similarly good partitions as the best competitor in terms of quality, hMetis, while being an order of magnitude faster. Our fastest configuration partitions the largest real-world graph in our study (it has 3.3 billion edges) with sequential code in about ten minutes while cutting less than half of the edges than the fastest competitor, kMetis.