Walking Randomly, Massively, and Efficiently
share
We introduce an approach that enables 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 Θ( n) MPC round complexity barrier. We design a PageRank algorithm that break this barrier even for directed graphs, and also show how to break this barrier for bipartiteness and expansion testing. 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 Θ( l) rounds on MPC. Moreover, we show that under 2-Cycle conjecture this round complexity is asymptotically tight. One of the most important application 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( n) rounds on undirected graphs (with Õ(m) total space), and Õ( n) rounds on directed graphs (with Õ(m+n^1+o(1)) total space). Building on our random-walk primitive and traditional property testing algorithms, we also show how to approximately test bipartiteness and expansion in O((n)) MPC rounds.
READ FULL TEXT