Linking the mixing times of random walks on static and dynamic random graphs
From MaRDI portal
Abstract: This paper considers non-backtracking random walks on random graphs generated according to the configuration model. The quantity of interest is the scaling of the mixing time of the random walk as the number of vertices of the random graph tends to infinity. Subject to mild general conditions, we link two mixing times: one for a static version of the random graph, the other for a class of dynamic versions of the random graph in which the edges are randomly rewired but the degrees are preserved. The link is provided by the probability that the random walk has not yet stepped along a previously rewired edge. We use this link to compute the scaling of the mixing time for three specific classes of random rewirings. Depending on the speed and the range of the rewiring relative to the current location of the random walk, the mixing time may exhibit no cut-off, one-sided cut-off or two-sided cut-off, a trichotomy that was also found in earlier work. Interestingly, for a class of dynamics that are `mesoscopic', i.e., non-local and non-global, we find new behaviour with six subregimes. Proofs are built on a new and flexible coupling scheme, in combination with sharp estimates on the degrees encountered by the random walk in the static and the dynamic version of the random graph. Some of these estimates require sharp control on possible short-cuts in the graph between the edges that are traversed by the random walk.
Recommendations
Cites work
- A comparison principle for random walk on dynamical percolation
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A threshold for cutoff in two-community random graphs
- Bounds on the Voter Model in Dynamic Networks
- Cover time and mixing time of random walks on dynamic graphs
- Cutoff at the ``entropic time for sparse Markov chains
- Cutoff for nonbacktracking random walks on sparse random graphs
- Cutoff for random walk on dynamical Erdős-Rényi graph
- Cutoff phenomena for random walks on random regular graphs
- Diameter in ultra-small scale-free random graphs
- Distances in random graphs with finite mean and infinite variance degrees
- Distances in random graphs with finite variance degrees
- Distributed computation in dynamic networks via random walks
- scientific article; zbMATH DE number 3661369 (Why is no real title available?)
- Mixing time for random walk on supercritical dynamical percolation
- Mixing time of PageRank surfers on sparse random digraphs
- Mixing time trichotomy in regenerating dynamic digraphs
- Mixing times of random walks on dynamic configuration models
- Random walk on sparse random digraphs
- Random walks on dynamic configuration models: a trichotomy
- Random walks on dynamic graphs: mixing times, hitting times, and return probabilities
- Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times
- Random walks on the random graph
- Randomized Rumor Spreading in Dynamic Graphs
- Regeneration-enriched Markov processes with application to Monte Carlo
- Speeding up Markov chains with deterministic jumps
- When is a scale-free graph ultra-small?
Cited in
(16)- Mixing times of random walks on dynamic configuration models
- Mixing time trichotomy in regenerating dynamic digraphs
- Correlation bounds, mixing and \(m\)-dependence under random time-varying network distances with an application to Cox-processes
- Eigentime identities for random walks on a family of treelike networks and polymer networks
- Random walks on dynamic configuration models: a trichotomy
- Mixing times for the rook's walk via path coupling
- Random walks on dynamic graphs: mixing times, hitting times, and return probabilities
- Mixing time of PageRank surfers on sparse random digraphs
- Mixing trichotomy for an Ehrenfest urn with impurities
- Mixing of fast random walks on dynamic random permutations
- Mixing trichotomy for random walks on directed stochastic block models
- Recurrence, transience and degree distribution for the tree builder random walk
- Restart perturbations for reversible Markov chains: trichotomy and pre-cutoff equivalence
- Gradual convergence for Langevin dynamics on a degenerate potential
- Mixing cutoff for simple random walks on the Chung-Lu digraph
- Dynamic random intersection graph: dynamic local convergence and giant structure
This page was built for publication: Linking the mixing times of random walks on static and dynamic random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2080276)
