Random walks on dynamic configuration models: a trichotomy

DOI10.1016/J.SPA.2018.09.010MaRDI QIDQ2274302zbMATH OpenOpenAlexWikidataFDO

Authors Hakan Güldaş, Remco van der Hofstad, Luca Avena, F. den Hollander

Publication date 19 September 2019

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.04824

zbMATH Keywords

configuration modelcutoffmixing timerandom dynamicsrandom walk

Mathematics Subject Classification ID

Processes in random environments (60K37) Dynamic critical phenomena in statistical mechanics (82C27)

Abstract: We consider a dynamic random graph on $n$ vertices that is obtained by starting from a random graph generated according to the configuration model with a prescribed degree sequence and at each unit of time randomly rewiring a fraction $alph{a}_n$ of the edges. We are interested in the mixing time of a random walk without backtracking on this dynamic random graph in the limit as $noinfty$, when $alph{a}_n$ is chosen such that $$. In [1] we found that, under mild regularity conditions on the degree sequence, the mixing time is of order $1/sqrtalph{a}_n$ when $$. In the present paper we investigate what happens when $$. It turns out that the mixing time is of order $logn$, with the scaled mixing time exhibiting a one-sided cutoff when $$ and a two-sided cutoff when $$. The occurrence of a one-sided cutoff is a rare phenomenon. In our setting it comes from a competition between the time scales of mixing on the static graph, as identified by Ben-Hamou and Salez [4], and the regeneration time of first stepping across a rewired edge.

Recommendations

• Mixing times of random walks on dynamic configuration models
• Linking the mixing times of random walks on static and dynamic random graphs
• Mixing time trichotomy in regenerating dynamic digraphs
• Random walks on the random graph
• Comparing mixing times on sparse random graphs

Cites work

• Cutoff for nonbacktracking random walks on sparse random graphs
• Mixing times of random walks on dynamic configuration models
• Random graphs and complex networks. Volume 1
• Random walks on the random graph

Cited in

(22)

• Mixing times of random walks on dynamic configuration models
• Mixing time trichotomy in regenerating dynamic digraphs
• Linking the mixing times of random walks on static and dynamic random graphs
• Cutoff for random lifts of weighted graphs
• Complex networks: structure and functionality
• Graphon-valued stochastic processes from population genetics
• The power of choice in random walks: An empirical study
• A threshold for cutoff in two-community random graphs
• Edge-attractor random walks on dynamic networks
• Mixing time of PageRank surfers on sparse random digraphs
• Cutoff for rewiring dynamics on perfect matchings
• Mixing time of random walk on dynamical random cluster
• 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
• The phase transition of the voter model on evolving scale-free networks
• Restart perturbations for reversible Markov chains: trichotomy and pre-cutoff equivalence
• Mixing cutoff for simple random walks on the Chung-Lu digraph
• Dynamic random intersection graph: dynamic local convergence and giant structure
• Bounds on mixing time for time-inhomogeneous Markov chains
• Functional central limit theorem for the subgraph count of the voter model on dynamic random graphs

This page was built for publication: Random walks on dynamic configuration models: a trichotomy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274302)