SEMINARIO
Luca Avena
(Leiden University, NL)
Martedi' 15 Gennaio 2019 ORE 11:30
Dipartimento di Matematica e Fisica
Universita' degli Studi Roma Tre
Largo San Leonardo Murialdo,1 - Pal.C - Aula 211
Titolo: Mixing time on dynamic configuration model
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