Exploration on Dynamic Networks
Referent: Frank den Hollander, Leiden University, The Netherlands
Veranstalter: Andreas Greven
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 characterising its relative importance within the set. The assignment is achieved by exploration.
Complex networks are modelled as random graphs. Search algorithms are modelled as random walks. The mixing time of a random walk on a random graph is the time it needs to approach its 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 one particular example, namely, a random graph with prescribed degrees. We investigate what happens to the mixing time when edges are randomly rewired while the exploration is in progress. We identify three regimes in the limit as the graph becomes large: fast, moderate, slow dynamics. These regimes exhibit surprising behaviour.
The lecture is targeted at a general mathematics audience. No prior knowledge is assumed of network theory or probability theory.
Joint work with Luca Avena (Leiden), Hakan Guldas (Leiden) and Remco van der Hofstad (Eindhoven).