Given a graph, a simple strategy for measuring the closeness of vertices is as follows. We initially associate to each vertex a random number, then update the value of each vertex by the average of the values of its neighbors, and perform this update a few times. The closeness between a pair of vertices is indicated by the difference of the two associated values. This closeness is inspired by the concepts used in Bootstrap Algebraic Multigrid in which it allows a better interpolation of low-residual errors.
In this talk, I will unravel the mystery of this simple process, explain the intuition behind it, and analyze its convergence properties. This measurement has been successfully used for solving (or improving the existing algorithms for) a number of combinatorial problems, including graph partitioning, maximum matching, minimum p-sum, etc. I will present the results in these scenarios, which show the superior usefulness of this closeness concept.