Exploration on Dynamic Networks - Joint PAD seminar
Analysis and Geometry Seminar
23rd October 2018, 3:00 pm – 4:00 pm
Howard House, 4th Floor Seminar Room
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 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 prescribed 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.
Note: unusual room.