EUVIMEDEUVIMED entdecken
Crossref

Efficient and Accurate PageRank Approximation on Large Graphs

Siyue Wu, Dingming Wu, Junyi Quan, Tsz Nam Chan, Kezhong Lu

Proceedings of the ACM on Management of Data · 01.10.2024 · 2 (4) · 1-26

DOI: 10.1145/3677132 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.09.2024. Verfasst von Siyue Wu und 4 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 82 Literaturangaben. Gefördert von: National Natural Science Foundation of China, GuangDong Basic and Applied Basic Research Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

PageRank is a commonly used measurement in a wide range of applications, including search engines, recommendation systems, and social networks. However, this measurement suffers from huge computational overhead, which cannot be scaled to large graphs. Although many approximate algorithms have been proposed for computing PageRank values, these algorithms are either (i) not efficient or (ii) not accurate. Worse still, some of them cannot provide estimated PageRank values for all the vertices. In this paper, we first propose the CUR-Trans algorithm, which can reduce the time complexity for computing PageRank values and has lower error bound than existing matrix approximation-based PageRank algorithms. Then, we develop the T 2 -Approx algorithm to further reduce the time complexity for computing this measurement. Experiment results on three large-scale graphs show that both the CUR-Trans algorithm and the T 2 -Approx algorithm achieve the lowest response time for computing PageRank values with the best accuracy (for the CUR-Trans algorithm) or the competitive accuracy (for the T 2 -Approx algorithm). Besides, the two proposed algorithms are able to provide estimated PageRank values for all the vertices.

Förderung

  • National Natural Science Foundation of China
  • GuangDong Basic and Applied Basic Research Foundation

Zitieren

APA

Wu, S., Wu, D., Quan, J., Chan, T. N., & Lu, K. (2024). Efficient and Accurate PageRank Approximation on Large Graphs. Proceedings of the ACM on Management of Data, 2(4), 1-26. https://doi.org/10.1145/3677132

Vancouver

Wu S, Wu D, Quan J, Chan TN, Lu K. Efficient and Accurate PageRank Approximation on Large Graphs. Proceedings of the ACM on Management of Data. 2024;2(4):1-26. doi:10.1145/3677132

BibTeX
@article{Wu2024,
  author = {Wu, Siyue and Wu, Dingming and Quan, Junyi and Chan, Tsz Nam and Lu, Kezhong},
  title = {Efficient and Accurate PageRank Approximation on Large Graphs},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2024},
  volume = {2},
  number = {4},
  pages = {1--26},
  doi = {10.1145/3677132}
}
Kostenlos starten →