Walking Randomly, Massively, and Efficiently

Monday, November 4, 2019 - 4:00pm to 5:00pm
Piotr Jankowski
University of Warsaw

We introduce an approach that allows for efficiently generating many
independent random walks in big graph models, such as the Massive
Parallel Computation (MPC) model. We consider the case where the space per
machine is strongly sublinear in the number of vertices. In this case, many
natural approaches for graph problems struggle to overcome the log(n) MPC round
complexity barrier. We design a PageRank algorithm that breaks this barrier
even for directed graphs.

In the undirected case, we start our random walks from the stationary
distribution, so we approximately know the empirical distribution of
their next steps. This way we can use doubling approach to prepare
continuations of sampled walks in advance. Our approach enables generating multiple
random walks of length l in O(log l) rounds on MPC. Moreover, we show
that under 2-Cycle conjecture this round complexity is asymptotically tight.
One of the most important applications of random walks is PageRank

We show how to use our approach to compute approximate PageRank w.h.p.
for constant damping factor:

- in O(log log n) rounds on undirected graphs (with almost linear total

- in O(log log^2 n) rounds on directed graphs  (with almost linear total

Our algorithm for directed graphs is based on a novel idea -- we define
a mixture of directed and undirected versions of the graph. This allows us
to start our sampling from the undirected case and then to move step by
step towards the directed case. In each step, we sample slightly more walks
to be able to estimate the stationary distribution for the next step.

Joint work with Jakub Łącki, Slobodan Mitrović, and Krzysztof Onak