Abstract:
We are interested in understanding the mixing time (i.e. the time to
reach equilibrium) for a discrete-time random walk moving on a network
changing over time in a random fashion. To this aim, we consider a
specific model where the underlying evolving network has n vertices,
it is initially sampled from the so-called configuration model (a
random graph ensemble with a prescribed vertex-degree sequence) and at
each time-unit a given  fraction of the edge set is randomly rewired.
We characterize the mentioned mixing-time for a random walk without
backtracking as a function of the fraction of rewired edges. This work
extends to a dynamic setup previous works on random walks on static
random graphs. In particular, we show that the mixing-time is
speeded-up by the presence of the edge-rewiring dynamics and depending
on whether such a dynamics is slow, moderate or fast, we show the
presence of so-called cutoff , half-cutoff, or absence of cutoff,
respectively. Joint work with Hakan Guldas, Remco van der Hofstad and Frank den
Hollander