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

random walkcutoffmixing timeconfiguration modelrandom dynamics

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

(13)

• A threshold for cutoff in two-community random graphs
• 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

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)