Networks

Random processes on dynamic random graphs

Summary

The key question underlying this project is the following. Does the rate at which a random process explores a random graph increase or decrease when the random graph changes from being static to being dynamic?

A key example is a random walk on a dynamic version of the configuration  model, in which edges are relocated while the degree numbers are  preserved. In this example the stationary distribution is independent of time. The question is how mixing times depend on the topology of the random graph, such as the hub-structure. The goal is to find out whether or not quantities such as mixing times or cover times are smaller in the dynamic graph setting than in the static graph setting. 
Other random processes of interest on the dynamic configuration model are exclusion dynamics (random hopping of particles) and flipping dynamics (random flipping of spins). For the exclusion dynamics the stationary distribution is independent of time, for the flipping dynamics it is not. These examples therefore allow us to study two distinct settings: one where only the degree numbers play a role and one where the full topology of the graph plays a role. While random walks, exclusion dynamics and flipping dynamics have attracted considerable attention in the area of random graphs, they have so far not been studied on dynamic random graphs. A further example of interest is simple random walk on a dynamic percolation cluster.
Supervisors Remco van der Hofstad (TU/e), Frank den Hollander (UL)
PhD-student Hakan Guldas
Location Leiden University (UL)