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 the practically successful partitioner DIBAP [Meyerhenke et al., JPDC 69(9):750–
761, 2009]. Our analysis reveals that BUBBLE-FOS/C, which yields well-shaped partitions in experiments, computes a relaxed solution to an edge cut minimizing binary quadratic program (BQP). It therefore provides the first substantial theoretical insights (beyond intuition) why BUBBLE-FOS/C (and therefore indirectly DIBAP) yields good experimental results. Moreover, we show that in bisections computed by BUBBLE-FOS/C, at least one of the two parts is connected. Using arguments based on random walk techniques, we prove that in vertex-transitive graphs actually both parts must be connected components each. All these results may help to eventually bridge the gap between practical and theoretical graph partitioning.

Keywords: 
Diffusive graph partitioning, relaxed cut optimization, disturbed diffusion.