Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00612
Efficient Point-to-Point Resistance Distance Queries in Large Graphs
Vol. 27, no. 1, pp. 35-44, 2023. Regular paper.
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.
 This work is licensed under the terms of the CC-BY license.
Submitted: October 2022.
Reviewed: December 2022.
Revised: January 2023.
Accepted: February 2023.
Final: February 2023.
Published: February 2023.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX