Engineering Algorithms for Partitioning Large Graphs

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

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.