CNS-0708307. Parts of this work were performed while the authors were affiliated with the

the date of receipt and acceptance should be inserted later Abstract 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., J. Parallel and Distrib. Computing, 69(9):750–761, 2009). We begin by studying the disturbed diffusion scheme FOS/C, which com-putes the similarity measure used inBubble-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 bal-ancing algorithms (Berenbrink et al., SODA’11). We then regard Bubble-FOS/C, which has been shown in previous experiments to produce solutions with good partition shapes and othe