Random walks on dynamic configuration models: a trichotomy

DOI10.1016/J.SPA.2018.09.010zbMATH Open1422.60162arXiv1803.04824OpenAlexW2964051670WikidataQ129152501 ScholiaQ129152501MaRDI QIDQ2274302FDOQ2274302

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)

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.

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

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

zbMATH Keywords

random walkcutoffmixing timeconfiguration modelrandom dynamics

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• Edge-attractor random walks on dynamic networks
• Graphon-valued stochastic processes from population genetics
• Cutoff for random lifts of weighted graphs
• Complex networks: structure and functionality
• Mixing time of random walk on dynamical random cluster
• The power of choice in random walks: An empirical study
• Mixing time trichotomy in regenerating dynamic digraphs
• Mixing trichotomy for an Ehrenfest urn with impurities
• Mixing time of PageRank surfers on sparse random digraphs
• Cutoff for rewiring dynamics on perfect matchings
• Mixing times of random walks on dynamic configuration models
• Linking the mixing times of random walks on static and dynamic random graphs
• A threshold for cutoff in two-community 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)