Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this paper, we focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample. All previous algorithms that compute a random walk sample of length as a subroutine always do so naively, i.e., in O( ) rounds. The main contribution of this paper is a fast distributed algorithm for performing random walks. We show that a random walk sample of length can be computed inÕ( 2/3 D 1/3 ) rounds on an undirected unweighted network, where D is the diameter of the network. 1 When = Ω(D log n), this is an improvement over the naive O( ) bound. (We show that Ω(min{D, }) is a lower bound and hence in general we cannot have a running time faster than the diameter of the graph.) We also show that our algorithm can be applied to speedup the more general MetropolisHastings sampling. We extend our algorithms to perform a large number, k, of random walks efficiently. We show how k destinations can be sampled inÕ ((k ) 2/3 D 1/3 ) rounds if k ≤ 2 andÕ((k ) 1/2 ) rounds otherwise. We also present faster algorithms for performing random walks of length larger than (or equal to) the mixing time of the underlying graph. Our techniques can be useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine.
The problem of performing just one walk was proposed in REF (for short, this problem will simply be called Single Random Walk in this paper), wherein the first sublinear time distributed algorithm was provided, requiringÕ( 2/3 D 1/3 ) rounds (Õ hides polylog(n) factors); this improves over the naive O( ) algorithm when the walk is long compared to the diameter of the network.
Fast distributed random walks
PODC '09
Mathematics Computer Science