LANS Publications

"Algebraic Distance on Graphs"

J. Chen and I. Safro

Preprint ANL/MCS-P1696-1009

Preprint Version: [pdf]

Measuring the connection strength between a pair of vertices in a graph is one of the most vital concerns in many graph applications. Simple measures such as edge weights may not be sufficient for capturing the local connectivity. In this paper, we consider a neighborhood of each graph vertex and propagate a certain property value through direct neighbors. We present a measure of the connection strength (called the algebraic distance) defined from an iterative process based on this consideration. The proposed measure is attractive in that the process is simple, linear, and easily parallelized. A rigorous analysis of the convergence property of the
process confirms the underlying intuition that vertices are mutually reinforced and that the local neighborhoods play an important role in influencing the vertex connectivity. We demonstrate the practical effectiveness of the proposed measure through several combinatorial optimization problems on graphs and hypergraphs.