Metropolis Walks on Dynamic Graphs

Recently, random walks on dynamic graphs have been studied because of its adaptivity to dynamical settings including real network analysis. However, previous works showed a tremendous gap between static and dynamic networks for the cover time of a lazy simple random walk: Although $O(n^3)$ cover time was shown for any static graphs of $n$ vertices, there is an edge-changing dynamic graph with an exponential cover time. We study a lazy Metropolis walk of Nonaka, Ono, Sadakane, and Yamashita (2010), which is a weighted random walk using local degree information. We show that this walk is robust to an edge-changing in dynamic networks: For any connected edge-changing graphs of $n$ vertices, the lazy Metropolis walk has the $O(n^2)$ hitting time, the $O(n^2\log n)$ cover time, and the $O(n^2)$ coalescing time, while those times can be exponential for lazy simple random walks. All of these bounds are tight up to a constant factor. At the heart of the proof, we give upper bounds of those times for any reversible random walks with a time-homogeneous stationary distribution.