Many random walks are faster than one

Noga Alon; Gady Kozma; Chen Avin; Zvi Lotker; Michal Koucky; Mark R. Tuttle

doi:10.1145/1378533.1378557

Many random walks are faster than one

Noga Alon, Gady Kozma, Chen Avin, Zvi Lotker, Michal Koucky, Mark R. Tuttle

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

72 Scopus citations

Abstract

We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time-the expected time required to visit every node in a graph at least once-and we show that for a large collection of interesting graphs, running many random walks in parallel jdelds a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected fit-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

Original language	English (US)
Title of host publication	SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures
Publisher	Association for Computing Machinery
Pages	119-128
Number of pages	10
ISBN (Print)	9781595939739
DOIs	https://doi.org/10.1145/1378533.1378557
State	Published - 2008
Event	20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08 - Munich, Germany Duration: Jun 14 2008 → Jun 16 2008

Publication series

Name	Annual ACM Symposium on Parallelism in Algorithms and Architectures

Other

Other	20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08
Country	Germany
City	Munich
Period	6/14/08 → 6/16/08

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Hardware and Architecture
Software

Keywords

Cover time
Distributed algorithms
Graph search
Random walks
Speed-up

Access to Document

10.1145/1378533.1378557

Fingerprint Dive into the research topics of 'Many random walks are faster than one'. Together they form a unique fingerprint.

Cite this

Alon, N., Kozma, G., Avin, C., Lotker, Z., Koucky, M., & Tuttle, M. R. (2008). Many random walks are faster than one. In SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures (pp. 119-128). (Annual ACM Symposium on Parallelism in Algorithms and Architectures). Association for Computing Machinery. https://doi.org/10.1145/1378533.1378557

@inproceedings{40e9aaaaeda24c13ac73f2b2dd689bc5,

title = "Many random walks are faster than one",

abstract = "We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time-the expected time required to visit every node in a graph at least once-and we show that for a large collection of interesting graphs, running many random walks in parallel jdelds a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected fit-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.",

keywords = "Cover time, Distributed algorithms, Graph search, Random walks, Speed-up",

author = "Noga Alon and Gady Kozma and Chen Avin and Zvi Lotker and Michal Koucky and Tuttle, {Mark R.}",

year = "2008",

doi = "10.1145/1378533.1378557",

language = "English (US)",

isbn = "9781595939739",

series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",

publisher = "Association for Computing Machinery",

pages = "119--128",

booktitle = "SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures",

}

Alon, N, Kozma, G, Avin, C, Lotker, Z, Koucky, M & Tuttle, MR 2008, Many random walks are faster than one. in SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures. Annual ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery, pp. 119-128, 20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08, Munich, Germany, 6/14/08. https://doi.org/10.1145/1378533.1378557

Many random walks are faster than one. / Alon, Noga; Kozma, Gady; Avin, Chen; Lotker, Zvi; Koucky, Michal; Tuttle, Mark R.

SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2008. p. 119-128 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Many random walks are faster than one

AU - Alon, Noga

AU - Kozma, Gady

AU - Avin, Chen

AU - Lotker, Zvi

AU - Koucky, Michal

AU - Tuttle, Mark R.

PY - 2008

Y1 - 2008

N2 - We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time-the expected time required to visit every node in a graph at least once-and we show that for a large collection of interesting graphs, running many random walks in parallel jdelds a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected fit-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

AB - We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time-the expected time required to visit every node in a graph at least once-and we show that for a large collection of interesting graphs, running many random walks in parallel jdelds a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected fit-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

KW - Cover time

KW - Distributed algorithms

KW - Graph search

KW - Random walks

KW - Speed-up

UR - http://www.scopus.com/inward/record.url?scp=57349120535&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57349120535&partnerID=8YFLogxK

U2 - 10.1145/1378533.1378557

DO - 10.1145/1378533.1378557

M3 - Conference contribution

AN - SCOPUS:57349120535

SN - 9781595939739

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 119

EP - 128

BT - SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08

Y2 - 14 June 2008 through 16 June 2008

ER -