Document Open Access Logo

Multiple Random Walks on Graphs: Mixing Few to Cover Many

Authors Nicolás Rivera , Thomas Sauerwald , John Sylvester

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.107.pdf
  • Filesize: 0.76 MB
  • 16 pages

Document Identifiers

Author Details

Nicolás Rivera
  • Department of Computer Science & Technology, University of Cambridge, UK
  • Instituto de Ingeniería Matemática, University of Valparaíso, Chile
Thomas Sauerwald
  • Department of Computer Science & Technology, University of Cambridge, UK
John Sylvester
  • Department of Computer Science & Technology, University of Cambridge, UK
  • School of Computing Science, University of Glasgow, UK

Funding

N.R., T.S. & J.S. were supported by ERC Starting Grant no. 679660 (DYNAMIC MARCH). N.R. was supported by FONDECYT grant number 3210805. J.S. was partially supported by ESPRC grant number EP/T004878/1.

Acknowledgements

We thank Jonathan Hermon for some interesting and useful discussions, and Przemysław Gordinowicz for his feedback on an earlier version of this paper.

Cite AsGet BibTex

Nicolás Rivera, Thomas Sauerwald, and John Sylvester. Multiple Random Walks on Graphs: Mixing Few to Cover Many. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 107:1-107:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.107

Abstract

Random walks on graphs are an essential primitive for many randomised algorithms and stochastic processes. It is natural to ask how much can be gained by running k multiple random walks independently and in parallel. Although the cover time of multiple walks has been investigated for many natural networks, the problem of finding a general characterisation of multiple cover times for worst-case start vertices (posed by Alon, Avin, Koucký, Kozma, Lotker, and Tuttle in 2008) remains an open problem. First, we improve and tighten various bounds on the stationary cover time when k random walks start from vertices sampled from the stationary distribution. For example, we prove an unconditional lower bound of Ω((n/k) log n) on the stationary cover time, holding for any n-vertex graph G and any 1 ≤ k = o(nlog n). Secondly, we establish the stationary cover times of multiple walks on several fundamental networks up to constant factors. Thirdly, we present a framework characterising worst-case cover times in terms of stationary cover times and a novel, relaxed notion of mixing time for multiple walks called the partial mixing time. Roughly speaking, the partial mixing time only requires a specific portion of all random walks to be mixed. Using these new concepts, we can establish (or recover) the worst-case cover times for many networks including expanders, preferential attachment graphs, grids, binary trees and hypercubes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Stochastic processes
Keywords
  • Multiple Random walks
  • Markov Chains
  • Random Walks
  • Cover Time

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. David Aldous and Persi Diaconis. Strong uniform times and finite random walks. Adv. in Appl. Math., 8(1):69-97, 1987. URL: https://doi.org/10.1016/0196-8858(87)90006-6.
  2. David Aldous and James Allen Fill. Reversible Markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014. URL: https://www.stat.berkeley.edu/~aldous/RWG/book.html.
  3. David J. Aldous. Lower bounds for covering times for reversible Markov chains and random walks on graphs. J. Theoret. Probab., 2(1):91-100, 1989. URL: https://doi.org/10.1007/BF01048272.
  4. Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pages 218-223. IEEE Computer Society, 1979. URL: https://doi.org/10.1109/SFCS.1979.34.
  5. Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, and Mark R. Tuttle. Many random walks are faster than one. Combin. Probab. Comput., 20(4):481-502, 2011. URL: https://doi.org/10.1017/S0963548311000125.
  6. Reid Andersen, Fan R. K. Chung, and Kevin J. Lang. Local graph partitioning using pagerank vectors. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 475-486. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/FOCS.2006.44.
  7. Anna Ben-Hamou, Roberto I. Oliveira, and Yuval Peres. Estimating graph parameters via random walks with restarts. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1702-1714. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.111.
  8. Lucas Boczkowski, Brieuc Guinard, Amos Korman, Zvi Lotker, and Marc P. Renault. Random walks with multiple step lengths. In Michael A. Bender, Martin Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pages 174-186. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_14.
  9. Andrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, and Eli Upfal. Trading space for time in undirected s-t connectivity. SIAM J. Comput., 23(2):324-334, 1994. URL: https://doi.org/10.1137/S0097539790190144.
  10. Colin Cooper and Alan Frieze. The cover time of the preferential attachment graph. J. Combin. Theory Ser. B, 97(2):269-290, 2007. URL: https://doi.org/10.1016/j.jctb.2006.05.007.
  11. Colin Cooper, Tomasz Radzik, and Yiannis Siantos. Estimating network parameters using random walks. Social Netw. Analys. Mining, 4(1):168, 2014. URL: https://doi.org/10.1007/s13278-014-0168-6.
  12. Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, and Christian Sohler. Planar graphs: Random walks and bipartiteness testing. Random Struct. Algorithms, 55(1):104-124, 2019. URL: https://doi.org/10.1002/rsa.20826.
  13. Artur Czumaj and Christian Sohler. Testing expansion in bounded-degree graphs. Comb. Probab. Comput., 19(5-6):693-709, 2010. URL: https://doi.org/10.1017/S096354831000012X.
  14. Jian Ding, James R. Lee, and Yuval Peres. Cover times, blanket times, and majorizing measures. Annals of Mathematics, 175(3):1409-1471, 2012. URL: https://doi.org/10.4007/annals.2012.175.3.8.
  15. Klim Efremenko and Omer Reingold. How well do random walks parallelize? In Irit Dinur, Klaus Jansen, Joseph Naor, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, volume 5687 of Lecture Notes in Computer Science, pages 476-489. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_36.
  16. Robert Elsässer and Thomas Sauerwald. Tight bounds for the cover time of multiple random walks. Theoret. Comput. Sci., 412(24):2623-2641, 2011. URL: https://doi.org/10.1016/j.tcs.2010.08.010.
  17. Uriel Feige. A tight lower bound on the cover time for random walks on graphs. Random Structures Algorithms, 6(4):433-438, 1995. URL: https://doi.org/10.1002/rsa.3240060406.
  18. Uriel Feige. A spectrum of time-space trade-offs for undirected s-t connectivity. J. Comput. Syst. Sci., 54(2):305-316, 1997. URL: https://doi.org/10.1006/jcss.1997.1471.
  19. Christos Gkantsidis, Milena Mihail, and Amin Saberi. Hybrid search schemes for unstructured peer-to-peer networks. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 13-17 March 2005, Miami, FL, USA, pages 1526-1537. IEEE, 2005. URL: https://doi.org/10.1109/INFCOM.2005.1498436.
  20. Brieuc Guinard and Amos Korman. Tight bounds for the cover times of random walks with heterogeneous step lengths. In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 28:1-28:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.28.
  21. Jonathan Hermon and Perla Sousi. Covering a graph with independent walks, 2021. URL: http://arxiv.org/abs/2104.00665.
  22. Andrej Ivaskovic, Adrian Kosowski, Dominik Pajak, and Thomas Sauerwald. Multiple random walks on paths and grids. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 44:1-44:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.44.
  23. David R. Karger and Matthias Ruhl. Simple efficient load balancing algorithms for peer-to-peer systems. In Phillip B. Gibbons and Micah Adler, editors, SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, June 27-30, 2004, Barcelona, Spain, pages 36-43. ACM, 2004. URL: https://doi.org/10.1145/1007912.1007919.
  24. David Kempe, Jon M. Kleinberg, and Alan J. Demers. Spatial gossip and resource location protocols. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 163-172. ACM, 2001. URL: https://doi.org/10.1145/380752.380796.
  25. Ralf Klasing, Adrian Kosowski, Dominik Pajak, and Thomas Sauerwald. The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks. In Panagiota Fatourou and Gadi Taubenfeld, editors, ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22-24, 2013, pages 365-374. ACM, 2013. URL: https://doi.org/10.1145/2484239.2484260.
  26. Akash Kumar, C. Seshadhri, and Andrew Stolman. Finding forbidden minors in sublinear time: A n^1/2+o(1)-query one-sided tester for minor closed properties on bounded degree graphs. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 509-520. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00055.
  27. Akash Kumar, C. Seshadhri, and Andrew Stolman. Random walks and forbidden minors II: a poly(d ε^-1)-query tester for minor-closed properties of bounded degree graphs. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 559-567. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316330.
  28. Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Walking randomly, massively, and efficiently. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 364-377. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384303.
  29. Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, and Yajun Wang. Information dissemination via random walks in d-dimensional space. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1612-1622. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.128.
  30. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. Google Scholar
  31. Pascal Lezaud. Chernoff-type bound for finite Markov chains. The Annals of Applied Probability, 8(3):849-867, 1998. URL: https://doi.org/10.1214/aoap/1028903453.
  32. László Lovász. Random walks on graphs: a survey. In Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 353-397. János Bolyai Math. Soc., Budapest, 1996. Google Scholar
  33. Qin Lv, Pei Cao, Edith Cohen, Kai Li, and Scott Shenker. Search and replication in unstructured peer-to-peer networks. In Kemal Ebcioglu, Keshav Pingali, and Alex Nicolau, editors, Proceedings of the 16th international conference on Supercomputing, ICS 2002, New York City, NY, USA, June 22-26, 2002, pages 84-95. ACM, 2002. URL: https://doi.org/10.1145/514191.514206.
  34. Milena Mihail, Christos H. Papadimitriou, and Amin Saberi. On certain connectivity properties of the internet topology. J. Comput. Syst. Sci., 72(2):239-251, 2006. URL: https://doi.org/10.1016/j.jcss.2005.06.009.
  35. Roberto I. Oliveira and Yuval Peres. Random walks on graphs: new bounds on hitting, meeting, coalescing and returning. In Marni Mishna and J. Ian Munro, editors, Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2019, San Diego, CA, USA, January 6, 2019, pages 119-126. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975505.13.
  36. Roberto Imbuzeiro Oliveira. Mixing and hitting times for finite Markov chains. Electron. J. Probab., 17:no. 70, 12, 2012. URL: https://doi.org/10.1214/EJP.v17-2274.
  37. Yuval Peres and Perla Sousi. Mixing times are hitting times of large sets. J. Theoret. Probab., 28(2):488-519, 2015. URL: https://doi.org/10.1007/s10959-013-0497-9.
  38. Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci, and Eli Upfal. Tight bounds on information dissemination in sparse mobile networks. In Cyril Gavoille and Pierre Fraigniaud, editors, Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011, pages 355-362. ACM, 2011. URL: https://doi.org/10.1145/1993806.1993882.
  39. Nicolás Rivera, Thomas Sauerwald, and John Sylvester. Multiple random walks on graphs: Mixing few to cover many, 2020. URL: http://arxiv.org/abs/2011.07893.
  40. Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali. Distributed random walks. J. ACM, 60(1):2:1-2:31, 2013. URL: https://doi.org/10.1145/2432622.2432624.
  41. Thomas Sauerwald. Expansion and the cover time of parallel random walks. In Andréa W. Richa and Rachid Guerraoui, editors, Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, July 25-28, 2010, pages 315-324. ACM, 2010. URL: https://doi.org/10.1145/1835698.1835776.
  42. Thomas Sauerwald and He Sun. Tight bounds for randomized load balancing on arbitrary network topologies. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 341-350. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.86.
  43. Daniel A. Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J. Comput., 42(1):1-26, 2013. URL: https://doi.org/10.1137/080744888.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact