![]() |
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.
![]() |
Submitted: October 2022.
Reviewed: December 2022.
Revised: January 2023.
Accepted: February 2023.
Final: February 2023.
Published: February 2023.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|