2026-07-26T19:18:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20233 2024-07-02T07:52:53Z ddc:004 open_access

Dynamic PageRank: Algorithms and Lower Bounds Jayaram, Rajesh Łącki, Jakub Mitrović, Slobodan Onak, Krzysztof Sankowski, Piotr PageRank dynamic algorithms graph algorithms We consider the PageRank problem in the dynamic setting, where the goal is to explicitly maintain an approximate PageRank vector π ∈ ℝⁿ for a graph under a sequence of edge insertions and deletions. Our main result is a complete characterization of the complexity of dynamic PageRank maintenance for both multiplicative and additive (L₁) approximations. First, we establish matching lower and upper bounds for maintaining additive approximate PageRank in both incremental and decremental settings. In particular, we demonstrate that in the worst-case (1/α)^{Θ(log log n)} update time is necessary and sufficient for this problem, where α is the desired additive approximation. On the other hand, we demonstrate that the commonly employed ForwardPush approach performs substantially worse than this optimal runtime. Specifically, we show that ForwardPush requires Ω(n^{1-δ}) time per update on average, for any δ > 0, even in the incremental setting. For multiplicative approximations, however, we demonstrate that the situation is significantly more challenging. Specifically, we prove that any algorithm that explicitly maintains a constant factor multiplicative approximation of the PageRank vector of a directed graph must have amortized update time Ω(n^{1-δ}), for any δ > 0, even in the incremental setting, thereby resolving a 13-year old open question of Bahmani et al. (VLDB 2010). This sharply contrasts with the undirected setting, where we show that poly log n update time is feasible, even in the fully dynamic setting under oblivious adversary. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rajesh Jayaram and Jakub Łącki and Slobodan Mitrović and Krzysztof Onak and Piotr Sankowski 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.90 urn:nbn:de:0030-drops-202336 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.90 eng https://creativecommons.org/licenses/by/4.0/legalcode