Engineering Algorithms for Partitioning Large Graphs

用于划分大图的工程算法

• 批准号: 183646693
• 负责人: Professor Dr. Peter Sanders
• 金额: --
• 依托单位: Lehrstuhl Algorithmik II
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2010
• 资助国家: 德国
• 起止时间: 2009-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/183646693?language=en
• 关键词: Engineering; Algorithms; Partitioning; Large; Graphs

Graph partitioning is very important for processing large graphs, e.g. networks stemming from finite element methods, route planning, social networks or web graphs. Often the node set of such graphs needs to be partitioned (or clustered) such that there are few edges between the blocks. In particular, when you process a graph in parallel on k processing elements, you often want to partition the graph into k blocks of about equal size so that there is as little interaction as possible between the blocks. During the first funding period our project was very successful. Our primary goal was to unleash the full potential of the multilevel approach for graph partitioning and related problems. In particular we aimed at a better understanding and an improvement of every component, i.e., contraction including edge ratings and matching, initial partitioning and refinement. On top of that we developed new techniques around multilevel approach, e.g., metaheuristics. One practical outcome was software that is world leading in some important aspects. More precisely, this encompasses highest quality partitions for almost all instances from the Walshaw benchmark set. En passant, we arrived at more powerful algorithms for graph clustering and partitioning and provided the most successful implementations as easy-to-use open source software. In the next project period, our primary goal is to extend our success from the previous project period to more general problems and their applications. Balanced graph partitioning for total cut minimization is only the tip of the iceberg of many related problems that have been less intensively studied but overall have at least an equally wide range of applications. While we expect many of our approaches from the basic problem to help with the more general ones, many new questions and difficulties arise. For example, if we want to partition hypergraphs, the basic approaches may transfer but we get at least two different objective functions and without further ideas, performance will drop dramatically. Further possible generalizations are allowing multiple objectives, and looking at dynamic situations where the graph changes over time. On the other hand, it is also important to look at specializations to families of graphs with particular properties that allow us to compute better solutions more efficiently. Lastly, we will push the envelope with respect to parallelization ranging from shared memory algorithms that better exploit the available hardware to the largest supercomputers where we also need to copartition the input graph and the interconnection network. As in the previous funding period, we will provide the most successful implementations as open source software.

图分区对于处理大型图非常重要，例如源于有限元方法、路线规划、社交网络或网络图的网络。 通常，此类图的节点集需要进行分区（或聚类），以使块之间的边很少。特别是，当您在 k 个处理元素上并行处理图时，您通常希望将图划分为 k 个大小大致相等的块，以便块之间的交互尽可能少。在第一个资助期间，我们的项目非常成功。我们的主要目标是充分发挥图分区和相关问题的多级方法的全部潜力。 特别是，我们的目标是更好地理解和改进每个组件，即包括边缘评级和匹配、初始划分和细化在内的收缩。 最重要的是，我们围绕多层次方法开发了新技术，例如元启发法。 一项实际成果是软件在某些重要方面处于世界领先地位。 更准确地说，这涵盖了 Walshaw 基准集中几乎所有实例的最高质量分区。 顺便说一句，我们得出了更强大的图聚类和分区算法，并提供了最成功的实现作为易于使用的开源软件。 在下一个项目期间，我们的首要目标是将我们从上一个项目期间的成功扩展到更普遍的问题及其应用。用于总割最小化的平衡图划分只是许多相关问题的冰山一角，这些问题的研究较少，但总体上至少具有同样广泛的应用。虽然我们期望从基本问题出发的许多方法能够帮助解决更普遍的问题，但仍然出现了许多新的问题和困难。 例如，如果我们想要划分超图，基本方法可能会转移，但我们至少得到两个不同的目标函数，如果没有进一步的想法，性能将急剧下降。 进一步可能的概括是允许多个目标，并查看图形随时间变化的动态情况。 另一方面，研究具有特定属性的图族的专业化也很重要，这些属性使我们能够更有效地计算更好的解决方案。 最后，我们将挑战并行化的极限，从更好地利用可用硬件的共享内存算法到最大的超级计算机，我们还需要对输入图和互连网络进行共同分区。与上一个资助期一样，我们将提供最成功的实施作为开源软件。