Seminario - Mixing time on dynamic configuration model

Link identifier #identifier__114671-1Link identifier #identifier__73898-2

15 Gennaio 2019, ore 11:30
Dipartimento di Matematica e Fisica, Aula 211
Largo San Leonardo Murialdo, 1 palazzina C - Roma

Martedì 15 gennaio 2019 alle ore 11.30, presso l'Aula 211, il Dipartimento di Matematica e Fisica, ospiterà il seminario del prof. Luca Avena dal titolo "Mixing time on dynamic configuration model".

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. 

Per informazioni:
Pietro Caputo
Link identifier

Link identifier single category #link-single-category-56072Eventi