Graph partitioning and disturbed diffusion

The NPNP-hard graph partitioning problem is an important subtask in load balancing and many other applications. It requires the division of a graph’s vertex set into P equally sized subsets such that some objective function is optimized. State-of-the-art libraries addressing this problem show several deficiencies: they are hard to parallelize, focus on small edge-cuts instead of few boundary vertices, and often produce disconnected partitions.This work introduces our novel graph partitioning and repartitioning heuristic Bubble-FOS/C. In contrast to other libraries, Bubble-FOS/C does not try to minimize the edge-cut explicitly, but focuses instead implicitly on good partition shapes. The shapes are optimized by diffusion processes that are embedded into an iterative framework. This approach incorporates a high degree of parallelism.Besides describing the evolution process that led to the new diffusion scheme FOS/C used by Bubble-FOS/C, we reveal some of FOS/C’s properties and propose a number of enhancements for a fast and reliable implementation. Our experiments, in which we compare sequential and parallel Bubble-FOS/C implementations to the state-of-the-art libraries Metis and Jostle, reveal that our new heuristic is slower, but generates high-quality solutions that are often superior.