Coloquio del IMUNAM - C. U. febrero 2024

Resumen: In my talk I will discuss techniques that allow for efficiently generating many independent random walks from starting from all nodes in a graph. This computational routine is often used for computing the PageRank vector which is a fundamental data science notion. I introduce how to implement such random walk generation in the context of the Massive Parallel Computation (MPC) model as well as dynamic computations. More specifically, I will discuss:

- how to maintain such a set of random walks in undirected graphs  in polylogarithimic update time,
- how to compute such a set of random walks in MPC model in polyloglog time.
These results immediately lead to efficient approximation algorithms for the PageRank problem in respective scenarios.

On the negative side we provide an Ω(n^{1−δ}) lower bound for the amortized update time of any algorithm that explicitly maintains a constant multiplicative approximation of PageRank in the insertion- or deletion-only model in directed graphs, what resolves a 13-year old open question of Bahmani et al. (VLDB 2010). In order to obtain efficient algorithms, we look beyond the relative error goal, and demonstrate that a simple batch recomputation algorithm can maintain good approximations to PageRank under L_1 error. We evaluate this similar algorithm empirically and demonstrate that it delivers similar preformacje while being much simpler .

Based on joint work with Rajesh Jayaram, Kuba Łącki, Slobodan Mitrović, Krzysztof Onak.

https://www.matem.unam.mx/actividades/coloquio/cu/actividades/parallel-and-dynamic-algorithms-for-pagerank-are-random-walks-necessary