Dynamic PageRank: Algorithms and Lower Bounds
<|reference_start|>Dynamic PageRank: Algorithms and Lower Bounds: We consider the PageRank problem in the dynamic setting, where the goal is to explicitly maintain an approximate PageRank vector $\pi \in \mathbb{R}^n$ 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_1$) 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/\alpha)^{\Theta(\log \log n)}$ update time is necessary and sufficient for this problem, where $\alpha$ 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 $\Omega(n^{1-\delta})$ time per update on average, for any $\delta > 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 $\Omega(n^{1-\delta})$, for any $\delta > 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 $\rm{poly}\ \log n$ update time is feasible, even in the fully dynamic setting under oblivious adversary.<|reference_end|>
@article{jayaram2024dynamic,
    title={Dynamic PageRank: Algorithms and Lower Bounds},
    author={Rajesh Jayaram, Jakub {L}k{a}cki, Slobodan Mitrovi'c, Krzysztof
  Onak, Piotr Sankowski},
    journal={arXiv preprint arXiv:2404.16267},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.16267},
    primaryClass={cs.DS}
}