Beyond good partition shapes: an analysis of diffusive graph partitioning In this paper we study the prevalent problem of graph partitioning by analyzing the diffusion-based partitioning heuristic B{sc ubble}-FOS/C, a key component of a practical successful graph partitioner [{it H. Meyerhenke}, {it B. Monien} and {it T. Sauerwald}, J. Parallel Distrib. Comput. 69, No. 9, 750--761 (2009)]. par We begin by studying the disturbed diffusion scheme FOS/C, which computes the similarity measure used in B{sc ubble}-FOS/C and is therefore the most crucial component. By relating FOS/C to random walks, we obtain precise characterizations of the behavior of FOS/C on tori and hypercubes. Besides leading to new knowledge on FOS/C (and therefore also on B{sc ubble}-FOS/C), these characterizations have been recently used for the analysis of load balancing algorithms [{it P. Berenbrink} et al., in: Proceedings of the 22nd Annual Symposium on Discrete Algorithms, 429--439 (2011)]. par We then regard B{sc ubble}-FOS/C, which has been shown in previous experiments to produce solutions with good partition shapes and other favorable properties. In this paper we prove that it computes a relaxed solution to an edge cut minimizing binary quadratic program (BQP). This result provides the first substantial theoretical insight why B{sc ubble}-FOS/C yields good experimental results in terms of graph partitioning metrics. Moreover, we show that in bisections computed by B{sc ubble}-FOS/C, at least one of the two parts is connected. Using the aforementioned relation between FOS/C and random walks, we prove that in vertex-transitive graphs both parts must be connected components.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element