Dynamic PageRank: Additive Error and Batch Recomputation

Explore the challenges and solutions in maintaining PageRank distributions for dynamic graphs in this 51-minute lecture by Jakub Lacki from Google Research. Delve into the complexities of efficiently updating PageRank values as edges are inserted or deleted from a graph. Discover why achieving constant factor multiplicative approximations of PageRank in dynamic settings is provably hard, resolving a long-standing open question. Learn about a simple yet effective batch recomputation algorithm that maintains good approximations under the L1 error metric. Gain insights from empirical evaluations showing this approach can be up to two orders of magnitude faster than existing dynamic baselines. Understand the trade-offs between relative error goals and practical performance in dynamic graph algorithms.