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

点击翻译按钮获取中文摘要

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.