Efficient Point-to-Point Resistance Distance Queries in Large Graphs

Abstract

We describe a method to efficiently compute point-to-point resistance distances in a graph, which are notoriously difficult to compute from the raw graph data. Our method is based on a relatively compact hierarchical data structure which ''compresses'' the resistance distance data present in a graph, constructed by a nested bisection of the graph using compact edge-cuts. Built and stored in a preprocessing step (which is amenable to massive parallel processing), efficient traversal of a small portion of this data structure supports efficient and exact answers to resistance distance queries. The size of the resulting data structure for a graph of $n$ vertices is $O(nk\log n)$, where $k$ is the size of a balanced edge-cut of the graph. Exact queries then require $O(k\log n)$ worst-case time and $O(k)$ average-case time. Approximate values may be obtained significantly faster by applying standard dimension reduction techniques to the ''coordinates'' stored in the structure.