Partitioning graphs into blocks of roughly equal size such that few edges run between blocks is a frequently needed operation in processing graphs. Recently, size, variety, and structural complexity of these networks has grown dramatically. Unfortunately, previous approaches to parallel graph partitioning have problems in this context since they often show a negative trade-off between speed and quality. We present an approach to multi-level shared-memory parallel graph partitioning that guarantees balanced solutions, shows high speed-ups for a variety of large graphs and yields very good quality independently of the number of cores used. For example, on 31 cores, our algorithm partitions our largest test instance into 16 blocks cutting less than half the number of edges than our main competitor when both algorithms are given the same amount of time. Important ingredients include parallel label propagation, parallel initial partitioning, a simple yet effective approach to parallel localized local search, and cache-aware hash tables.

We develop a fast and high quality multilevel algorithm that directly partitions hypergraphs into k balanced blocks – without the detour over recursive bipartitioning. In particular, our algorithm efficiently implements the powerful FM local search heuristics for the complicated k-way case. This is important for objective functions which depend on the number of blocks connected by a hyperedge. We also remove several further bottlenecks in processing large hyperedges, develop a faster contraction algorithm, and a new adaptive stopping rule for local search. To further reduce the size of hyperedges, we develop a pin-sparsifier based on the min-hashing technique that clusters vertices with similar neighborhood. Extensive experiments indicate that our KaHyPar-partitioner compares favorably with the best previous systems. KaHyPar is faster than hMetis and computes better solutions. KaHyPar's results are considerably better than the (faster) PaToH partitioner.

We design and implement a distributed algorithm for balanced k -way hypergraph partitioning that minimizes fanout, a fundamental hypergraph quantity also known as the communication volume and ( k - 1)-cut metric, by optimizing a novel objective called probabilistic fanout. This choice allows a simple local search heuristic to achieve comparable solution quality to the best existing hypergraph partitioners. Our algorithm is arbitrarily scalable due to a careful design that controls computational complexity, space complexity, and communication. In practice, we commonly process hypergraphs with billions of vertices and hyperedges in a few hours. We explain how the algorithm's scalability, both in terms of hypergraph size and bucket count, is limited only by the number of machines available. We perform an extensive comparison to existing distributed hypergraph partitioners and find that our approach is able to optimize hypergraphs roughly 100 times bigger on the same set of machines. We call the resulting tool Social Hash Partitioner , and accompanying this paper, we open-source the most scalable version based on recursive bisection.

Using (a, b)-trees as an example, we show how to perform a parallel split with logarithmic latency and parallel join, bulk updates, intersection, union (or merge), and (symmetric) set difference with logarithmic latency and with information theoretically optimal work. We present both asymptotically optimal solutions and simplified versions that perform well in practice - they are several times faster than previous implementations.

In this paper, we develop semi-external and external memory algorithms for graph partitioning and clustering problems. Graph partitioning and clustering are key tools for processing and analyzing large complex networks. We address both problems in the (semi-)external model by adapting the size-constrained label propagation technique. Our (semi-)external size-constrained label propagation algorithm can be used to compute graph clusterings and is a prerequisite for the (semi-)external graph partitioning algorithm. The algorithm is then used for both the coarsening and the refinement phase of a multilevel algorithm to compute graph partitions. Our algorithm is able to partition and cluster huge complex networks with billions of edges on cheap commodity machines. Experiments demonstrate that the semi-external graph partitioning algorithm is scalable and can compute high quality partitions in time that is comparable to the running time of an efficient internal memory implementation. A parallelization of the algorithm in the semi-external model further reduces running time.