Abstract
We consider the PageRank problem in the dynamic setting, where the goal is to efficiently maintain an approximate PageRank distribution for a graph under a sequence of edge insertions and deletions.
Despite the common goal of obtaining relative error approximations to PageRank, we show that this is provably hard in the dynamic setting. Namely, we prove that any algorithm that keeps track of a constant factor multiplicative approximation of PageRank of an n-vertex graph over a sequence of n updates must, in the worst case, run in at least n^(1-epsilon) time, for any constant epsilon > 0, even if only insertions are allowed. This resolves a 13-year-old open question of Bahmani et al.~(VLDB 2010).
To develop efficient algorithms, we look beyond the relative error goal, and demonstrate that a simple batch recomputation algorithm can maintain good approximations to PageRank under the L1 error metric. We evaluate this simple algorithm empirically and find that it is up to two orders of magnitude faster than the existing dynamic baselines.