Algorithm Engineering for Dynamic and (Re)Streaming Graph Decomposition Algorithms

处理大型复杂网络最近引起了相当大的兴趣。有时，这些网络由数十亿个实体组成，这些实体产生了新兴的属性和结构。分解和分析这些结构有助于我们获得对周围环境的新见解。随着庞大的网络变得丰富，需要可扩展的算法来执行分析。图分区问题要求将一个图划分为k个大小相等的块，这些块之间几乎没有边。在实践中，启发式算法主要用于解决这一问题。在过去的十年中，我们开发了领先的（超）图分解的多层代码，例如图划分（KaHIP）或超图划分（KaHyPar）。到目前为止，我们的算法在社区中已经得到了很好的验证，并且被认为是为手头的问题计算最佳解决方案的算法。这一成功是通过对算法工程方法的示范使用来实现的。通常，底层图形或输入实例会随着时间的推移而变化，例如，随着时间的推移，顶点或边会被插入或删除。因此，在过去的几十年里，已经发现了一整套用于动态图的算法和数据结构。另一方面，分解问题的（再）流算法目前是一个新兴的领域。在流模型中，节点一次到达一个，并且必须直接做出块分配决策。目前，对于非常大的图，在实践中观察到一个差距：与内部内存竞争对手相比，当前最先进的流算法计算的分区质量低得多。该项目的主要焦点是动态和（重新）流图划分/分解的算法。动态和流版本的问题在实践中没有得到很好的解决。我们将应用算法工程方法来解决这些问题，以获得比以前更快的算法，并产生更好的解决方案。例如，我们将通过动态化多层方法的所有组件来设计最先进的动态算法。该项目还将缩小目前在（re）蒸汽算法中观察到的差距，并结合两个世界的优点：我们将设计一个快速流算法，该算法使用多层次和最新的高质量局部搜索思想，从而产生高质量的图分区，即使图的边缘不适合机器的内存，也可以在单个节点上计算。此外，我们将使用共享内存并行化来减少进一步计算分区所需的运行时间。

Processing large complex networks recently attracted considerable interest. Sometimes these networks are composed of billions of entities that give rise to emerging properties and structures. Decomposing and analyzing these structures aids us in gaining new insights about our surroundings. As huge networks become abundant, there is a need for scalable algorithms to perform analysis. The graph partitioning problem asks for a partition of a graph into k blocks of about equal size such that there are few edges between them. Heuristic algorithms are mostly used in practice to solve this problem. In last decade, we developed the leading multilevel codes for (hyper) graph decomposition, e.g. for graph partitioning (KaHIP) or for hypergraph partitioning (KaHyPar). By now, our algorithms are well-established in the communities and known as the algorithms computing the best solutions for the respected problem at hand. This success is achieved by an exemplary use of the algorithm engineering methodology. Often the underlying graphs or input instances change over time, i.e. vertices or edges are inserted or deleted while time is passing. Hence, a whole body of algorithms and data structures for dynamic graphs has been discovered in the last decades. On the other hand, (re)streaming algorithms for decomposition problems are currently an emerging field. In the streaming model, nodes arrive one at a time and block assignment decisions have to be made directly. Currently, there is a gap observed in practice for very large graphs: current state-of-the-art streaming algorithms compute much lower partition quality compared to their internal memory competitors. The main focus of the project are algorithms for dynamic and (re)streaming graph partitioning/decomposition. Dynamic and streaming versions of the problems are not sufficiently well solved in practice. We will apply the algorithm engineering methodology to those problems to arrive at algorithms that are significantly faster and produce considerably better solutions than previously possible. For example, we will engineer state-of-the-art dynamic algorithms by dynamizing all components of the multilevel approach. The project will also close the gap currently observed in (re)steaming algorithms and combine the best of the two worlds: we will engineer a fast streaming algorithm that uses multi-level and recent high-quality local search ideas and hence produces high-quality partitions of graphs that can be computed on single nodes even if the edges of the graph do not fit into the memory of the machine. Additionally, we will use shared-memory parallelization to reduce the necessary running time to compute partitions further.