Exploration On Dynamic Networks

Search algorithms on networks are important tools for the organisation of large data sets. A key example is Google PageRank, which assigns a numerical weight to each webpage, with the purpose of measuring its relative importance. The weighting is achieved by exploration. 

Networks are modelled as graphs, complex networks as random graphs, and search algorithms as random walks. The mixing time of a random walk on a random graph is the time it needs to approach its stationary distribution. 

Many real-world networks are dynamic in nature. In this talk we investigate what happens when at each unit of time a certain fraction of the edges is randomly rewired. We investigate three regimes: fast, moderate and slow dynamics. The mixing time in these regimes exhibits surprising behaviour.