You are not logged in |
Walking Randomly, Massively, and Efficiently
- Speaker(s)
- Piotr Sankowski
- Affiliation
- University of Warsaw
- Date
- Nov. 14, 2019, 12:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Algorithms
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 computation. 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 space),
- in O(log log^2 n) rounds on directed graphs (with almost linear total space).
Our algorithm for directed graphs is based on a novel idea -- we define a mixture of directed and undirected versions of the graph. This allow 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.
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 computation. 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 space),
- in O(log log^2 n) rounds on directed graphs (with almost linear total space).
Our algorithm for directed graphs is based on a novel idea -- we define a mixture of directed and undirected versions of the graph. This allow 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
