License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.93
URN: urn:nbn:de:0030-drops-106696
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10669/
Go to the corresponding LIPIcs Volume Portal

Sauerwald, Thomas ; Zanetti, Luca

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

pdf-format:
LIPIcs-ICALP-2019-93.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{sauerwald_et_al:LIPIcs:2019:10669,
  author =	{Thomas Sauerwald and Luca Zanetti},
  title =	{{Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{93:1--93:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10669},
  URN =		{urn:nbn:de:0030-drops-106696},
  doi =		{10.4230/LIPIcs.ICALP.2019.93},
  annote =	{Keywords: random walks, dynamic graphs, hitting times}
}

Keywords: random walks, dynamic graphs, hitting times
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI