Measuring the Connection Strengths between Graph Vertices

Event Sponsor: 
LANS Informal Seminar
Start Date: 
Aug 12 2009 - 3:00pm to 4:00pm
Building 221 Conference Room A261
Argonne National Laboratory
Jie Chen
Speaker(s) Title: 
Givens Associate, MCS

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.

Miscellaneous Information: