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

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.