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., 2009). 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., 2011). 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.
