Distributed random walks

DOI10.1145/2432622.2432624MaRDI QIDQ5395702zbMATH OpenOpenAlexWikidataFDO

Authors Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali

Publication date 17 February 2014

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.4544

zbMATH Keywords

distributed algorithmsrandom samplingrandom walksmixing timerandom spanning treedecentralized computation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Random walks on graphs (05C81) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)

Abstract: 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 sampling random walks efficiently in a distributed network and its applications. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain random walk samples. All previous algorithms that compute a random walk sample of length $ell$ as a subroutine always do so naively, i.e., in $O(ell)$ rounds. The main contribution of this paper is a fast distributed algorithm for performing random walks. We present a sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length $ell$ in $ildeO(sqrtellD)$ rounds ($ildeO$ hides $polylogn$ factors where $n$ is the number of nodes in the network) with high probability on an undirected network, where $D$ is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive $O(ell)$ bound. Furthermore, our algorithm is optimal within a poly-logarithmic factor as there exists a matching lower bound [Nanongkai et al. PODC 2011]. We further extend our algorithms to efficiently perform $k$ independent random walks in $ildeO(sqrtkellD+k)$ rounds. We also show that our algorithm can be applied to speedup the more general Metropolis-Hastings sampling. Our random walk algorithms can be used to speed up distributed algorithms in applications that use random walks as a subroutine, such as computing a random spanning tree and estimating mixing time and related parameters. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.

Recommendations

• Efficient distributed random walks with applications
• Fast distributed random walks
• Distributed computation in dynamic networks via random walks
• Fast distributed computation in dynamic networks via random walks
• A tight unconditional lower bound on distributed randomwalk computation

Cited in

(22)

• Fast distributed computation in dynamic networks via random walks
• Fast distributed PageRank computation
• Multiple random walks on graphs: mixing few to cover many
• scientific article; zbMATH DE number 1305416 (Why is no real title available?)
• A two-sided error distributed property tester for conductance
• A tight unconditional lower bound on distributed randomwalk computation
• Sampling-based algorithm for link prediction in temporal networks
• Aggregation is the key to succeed in random walks
• Estimating graph parameters with random walks
• Efficient distributed random walks with applications
• Fast distributed random walks
• Random walks, heat equation and distributed algorithms
• Towards communication-efficient Peer-to-Peer networks
• Multiple random walks on graphs: mixing few to cover many
• A parallel pagerank algorithm for undirected graph
• Improving resource location with locally precomputed partial random walks
• How to compute times of random walks based distributed algorithms
• Time- and communication-efficient overlay network construction via gossip
• What can be sampled locally?
• How Well Do Random Walks Parallelize?
• Distributed computation in dynamic networks via random walks
• Improving random walk estimation accuracy with uniform restarts

This page was built for publication: Distributed random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395702)