EUVIMEDEUVIMED entdecken
Crossref

Efficient Resistance Distance Computation: The Power of Landmark-based Approaches

Meihao Liao, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen, Hongchao Qin, Guoren Wang

Proceedings of the ACM on Management of Data · 26.05.2023 · 1 (1) · 1-27

DOI: 10.1145/3588922 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2023. Verfasst von Meihao Liao und 5 weiteren Autor:innen. Die Arbeit wurde bisher 17-mal zitiert (Crossref) und nennt 64 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Resistance distance is a fundamental metric to measure the similarity between two nodes in graphs which has been widely used in many real-world applications. In this paper, we study two problems on approximately computing resistance distance: (i) single-pair query which aims at calculating the resistance distance r(s, t) for a given pair of nodes (s, t); and (ii) single-source query which is to compute all the resistance distances r(s, u) for all nodes u in the graph with a given source node s. Existing algorithms for these two resistance distance query problems are often costly on large graphs. To efficiently solve these problems, we first establish several interesting connections among resistance distance, a new concept called v-absorbed random walk, random spanning forests, and a newly-developed v-absorbed push procedure. Based on such new connections, we propose three novel and efficient sampling-based algorithms as well as a deterministic algorithm for single-pair query; and we develop an online and two index-based approximation algorithms for single-source query. We show that the two index-based algorithms for single-source query take almost the same running time as the algorithms for single-pair query with the aid of a linear-size index. The striking feature of all our algorithms is that they are allowed to select an easy-to-hit node by random walks on the graph. Such an easy-to-hit landmark node v can make the v-absorbed random walk sampling, spanning tree sampling, as well as the v-absorbed push more efficient, thus significantly improving the performance of our algorithms. Extensive experiments on 5 real-life datasets show that our algorithms substantially outperform the state-of-the-art algorithms for two resistance distance query problems in terms of both running time and estimation errors.

Zitieren

APA

Liao, M., Li, R., Dai, Q., Chen, H., Qin, H., & Wang, G. (2023). Efficient Resistance Distance Computation: The Power of Landmark-based Approaches. Proceedings of the ACM on Management of Data, 1(1), 1-27. https://doi.org/10.1145/3588922

Vancouver

Liao M, Li R, Dai Q, Chen H, Qin H, Wang G. Efficient Resistance Distance Computation: The Power of Landmark-based Approaches. Proceedings of the ACM on Management of Data. 2023;1(1):1-27. doi:10.1145/3588922

BibTeX
@article{Liao2023,
  author = {Liao, Meihao and Li, Rong-Hua and Dai, Qiangqiang and Chen, Hongyang and Qin, Hongchao and Wang, Guoren},
  title = {Efficient Resistance Distance Computation: The Power of Landmark-based Approaches},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2023},
  volume = {1},
  number = {1},
  pages = {1--27},
  doi = {10.1145/3588922}
}
Kostenlos starten →