Document Open Access Logo

Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities

Authors Thomas Sauerwald, Luca Zanetti

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.93.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Thomas Sauerwald
  • Department of Computer Science and Technology, University of Cambridge, United Kingdom
Luca Zanetti
  • Department of Computer Science and Technology, University of Cambridge, United Kingdom

Funding

  • Sauerwald, Thomas: This project is partially funded by the ERC Starting Grant (DYNAMIC MARCH).
  • Zanetti, Luca: This project is partially funded by the ERC Starting Grant (DYNAMIC MARCH).

Cite AsGet BibTex

Thomas Sauerwald and Luca Zanetti. Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 93:1-93:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.93

Abstract

We establish and generalise several bounds for various random walk quantities including the mixing time and the maximum hitting time. Unlike previous analyses, our derivations are based on rather intuitive notions of local expansion properties which allow us to capture the progress the random walk makes through t-step probabilities. We apply our framework to dynamically changing graphs, where the set of vertices is fixed while the set of edges changes in each round. For random walks on dynamic connected graphs for which the stationary distribution does not change over time, we show that their behaviour is in a certain sense similar to static graphs. For example, we show that the mixing and hitting times of any sequence of d-regular connected graphs is O(n^2), generalising a well-known result for static graphs. We also provide refined bounds depending on the isoperimetric dimension of the graph, matching again known results for static graphs. Finally, we investigate properties of random walks on dynamic graphs that are not always connected: we relate their convergence to stationarity to the spectral properties of an average of transition matrices and provide some examples that demonstrate strong discrepancies between static and dynamic graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • random walks
  • dynamic graphs
  • hitting times

Metrics

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

Related Versions

References

  1. David Aldous and Jim Fill. Reversible Markov chains and random walks on graphs. unpublished monograph, 2002. Google Scholar
  2. Nima Anari and Shayan Oveis Gharan. Effective Resistance and Simple Random Walks. unpublished, 2014. URL: https://homes.cs.washington.edu/~shayan/courses/cse599/adv-approx-4.pdf.
  3. John Augustine, Gopal Pandurangan, and Peter Robinson. Distributed Algorithmic Foundations of Dynamic Networks. SIGACT News, 47(1):69-98, 2016. Google Scholar
  4. Chen Avin, Michal Koucký, and Zvi Lotker. Cover time and mixing time of random walks on dynamic graphs. Random Structures Algorithms, 52(4):576-596, 2018. Google Scholar
  5. Itai Benjamini and Gady Kozma. A resistance bound via an isoperimetric inequality. Combinatorica, 25(6):645-650, 2005. Google Scholar
  6. Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. Bounds on the voter model in dynamic networks. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), pages 146:1-146:15, July 12-15 2016. Google Scholar
  7. Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Trans. Inform. Theory, 52(6):2508-2530, 2006. Google Scholar
  8. Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. Comput. Complexity, 6(4):312-340, 1996/97. Google Scholar
  9. Andrea E. F. Clementi, Pierluigi Crescenzi, Carola Doerr, Pierre Fraigniaud, Francesco Pasquale, and Riccardo Silvestri. Rumor spreading in random evolving graphs. Random Struct. Algorithms, 48(2):290-312, 2016. Google Scholar
  10. Andrea E. F. Clementi, Claudio Macci, Angelo Monti, Francesco Pasquale, and Riccardo Silvestri. Flooding Time of Edge-Markovian Evolving Graphs. SIAM J. Discrete Math., 24(4):1694-1712, 2010. Google Scholar
  11. Andrea E. F. Clementi, Riccardo Silvestri, and Luca Trevisan. Information spreading in dynamic graphs. Distributed Computing, 28(1):55-73, 2015. Google Scholar
  12. Oksana Denysyuk and Luís E. T. Rodrigues. Random Walks on Evolving Graphs with Recurring Topologies. In Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings, pages 333-345, 2014. Google Scholar
  13. Robert Elsässer, Burkhard Monien, and Stefan Schamberger. Load Balancing in Dynamic Networks. In 7th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2004), 10-12 May 2004, Hong Kong, SAR, China, pages 193-200, 2004. Google Scholar
  14. Uriel Feige. A Tight Lower Bound on the Cover Time for Random Walks on Graphs. Random Struct. Algorithms, 6(4):433-438, 1995. URL: http://dx.doi.org/10.1002/rsa.3240060406.
  15. Uriel Feige. A Tight Upper Bound on the Cover Time for Random Walks on Graphs. Random Struct. Algorithms, 6(1):51-54, 1995. URL: http://dx.doi.org/10.1002/rsa.3240060106.
  16. James Allen Fill. Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Probab., 1(1):62-87, 1991. Google Scholar
  17. Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, and David Zuckerman. Tight Analyses of Two Local Load Balancing Algorithms. SIAM J. Comput., 29(1):29-64, 1999. URL: http://dx.doi.org/10.1137/S0097539795292208.
  18. George Giakkoupis, Thomas Sauerwald, and Alexandre Stauffer. Randomized Rumor Spreading in Dynamic Graphs. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 495-507, 2014. Google Scholar
  19. Sharad Goel, Ravi Montenegro, and Prasad Tetali. Mixing time bounds via the spectral profile. Electron. J. Probab., 11:1-26, 2006. Google Scholar
  20. Jonathan Hermon and Perla Sousi. Random walk on dynamical percolation. arXiv preprint, 2019. URL: http://arxiv.org/abs/1902.02770.
  21. Varun Kanade, Frederik Mallmann-Trenn, and Thomas Sauerwald. On coalescence time in graphs: When is coalescing as fast as meeting? In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 956-965, 2019. Google Scholar
  22. Fabian Kuhn, Nancy A. Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 513-522, 2010. Google Scholar
  23. Fabian Kuhn and Rotem Oshman. Dynamic networks: models and algorithms. SIGACT News, 42(1):82-96, 2011. Google Scholar
  24. Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, and Yajun Wang. Information dissemination via random walks in d-dimensional space. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1612-1622, 2012. Google Scholar
  25. Ioannis Lamprou, Russell Martin, and Paul Spirakis. Cover time in edge-uniform stochastically-evolving graphs. Algorithms (Basel), 11(10):Paper No. 149, 15, 2018. Google Scholar
  26. David A. Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Society, Providence, RI, 2017. Google Scholar
  27. László Lovász and Ravi Kannan. Faster mixing via average conductance. In 31st Annual ACM Symposium on Theory of Computing, pages 282-287. ACM, 1999. Google Scholar
  28. Othon Michail and Paul G. Spirakis. Elements of the theory of dynamic networks. Commun. ACM, 61(2):72, 2018. URL: http://dx.doi.org/10.1145/3156693.
  29. Yuval Peres, Alistair Sinclair, Perla Sousi, and Alexandre Stauffer. Mobile Geometric Graphs: Detection, Coverage and Percolation. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 412-428, 2011. Google Scholar
  30. Yuval Peres, Alexandre Stauffer, and Jeffrey E. Steif. Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times. Probab. Theory Related Fields, 162(3-4):487-530, 2015. Google Scholar
  31. Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci, and Eli Upfal. Tight bounds on information dissemination in sparse mobile networks. In 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, 2011. Google Scholar
  32. Laurent Saloff-Coste and Jessica Zúñiga. Merging for time inhomogeneous finite Markov chains. I. Singular values and stability. Electron. J. Probab., 14:1456-1494, 2009. Google Scholar
  33. Laurent Saloff-Coste and Jessica Zúñiga. Merging for inhomogeneous finite Markov chains, Part II: Nash and log-Sobolev inequalities. Ann. Probab., 39(3):1161-1203, 2011. Google Scholar
  34. Atish Das Sarma, Anisur Rahaman Molla, and Gopal Pandurangan. Distributed computation in dynamic networks via random walks. Theor. Comput. Sci., 581:45-66, 2015. Google Scholar
  35. Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93-133, 1989. Google Scholar
  36. Perla Sousi and Sam Thomas. Cutoff for Random Walk on Dynamical Erdos-Renyi graph. arXiv preprint, 2018. URL: http://arxiv.org/abs/1807.04719.
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