Home DF* PageRank: Incrementally Expanding Approaches for Updating PageRank on Dynamic Graphs

Publications

DF* PageRank: Incrementally Expanding Approaches for Updating PageRank on Dynamic Graphs

Author : Dr Subhajit Sahu

Year : 2024

Publisher : Springer Science and Business Media Deutschland GmbH

Source Title : Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Document Type :

Abstract

PageRank is a widely used centrality measure that assesses the significance of vertices in a graph. Efficiently updating PageRank on dynamic graphs is essential for various applications due to the increasing scale of datasets. This paper introduces our Dynamic Frontier (DF) and Dynamic Frontier with Pruning (DF-P) approaches (https://github.com/puzzlef/pagerank-openmp-dynamic). Given a batch update comprising edge insertions and deletions, these approaches iteratively identify vertices likely to change their ranks with minimal overhead. On a server featuring a 64-core AMD EPYC-7742 processor, our approaches outperform Static and Dynamic Traversal PageRank by 5.2×/15.2× and 1.3×/3.5× respectively – on real-world dynamic graphs, and by 7.2×/9.6× and 4.0×/5.6× on large static graphs with random batch updates. Our approaches scale at a rate of 1.8×/1.7× for every doubling of threads.