Beyond Good Partition Shapes: An Analysis of Diffusive Graph Partitioning

作者：Meyerhenke Henning^*; Sauerwald Thomas

来源：Algorithmica, 2012, 64(3): 329-361.

DOI：10.1007/s00453-012-9666-y

• Diffusive graph partitioning
• Relaxed cut optimization
• Disturbed diffusion
• Random walks

In this paper we study the prevalent problem of graph partitioning by analyzing the diffusion-based partitioning heuristic Bubble-FOS/C, a key component of a practical successful graph partitioner (Meyerhenke et al. in J. Parallel Distrib. Comput. 69(9):750-761, 2009). %26lt;br%26gt;We begin by studying the disturbed diffusion scheme FOS/C, which computes the similarity measure used in Bubble-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 Bubble-FOS/C), these characterizations have been recently used for the analysis of load balancing algorithms (Berenbrink et al. in Proceedings of the 22nd Annual Symposium on Discrete Algorithms, pp. 429-439, 2011). %26lt;br%26gt;We then regard Bubble-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 Bubble-FOS/C yields good experimental results in terms of graph partitioning metrics. Moreover, we show that in bisections computed by Bubble-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.

• 出版日期2012-11