Exploration on Dynamic Networks
Search algorithms on networks are important tools for the organization of large data sets. A key example is Google PageRank, which assigns a numerical weight to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of measuring its relative importance within the set. The weighting is achieved by exploration.
The mixing time of a random walk on a random graph is the time it needs to approach its stationary distribution (also called equilibrium distribution). The characterisation of the mixing time has been the subject of intensive study. Many real-world networks are dynamic in nature. It is therefore natural to study random walks on dynamic random graphs.
In this talk we focus on a random graph with rescribed degrees. We investigate what happens to the mixing time of the random walk when at each unit of time a certain fraction of the edges is randomly rewired. We identify three regimes in the limit as the graph becomes large: fast, moderate, slow dynamics. These regimes exhibit surprising behaviour.
The talk is aimed at a general mathematics audience. No prior knowledge of probability theory or graph theory is required.
