Plücker Lecture 2019 by Frank den Hollander

Frank den Hollander, University of Leiden

Titel: Exploration on Dynamic Networks

Part one: Trichotomy

Time: 16.15-17.00, 21 October 2019

Part two: Comparison

Time: 17.30-18:15, 21 October 2019

Abstract:

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. A hyperlink counts as a vote of support. The PageRank of a page is defined recursively, and depends on the number and the weight of all the pages that link to it. A page that is linked to by many pages with a high rank receives a high rank itself.

Real-world networks are modelled as graphs, consisting of a set of vertices and a set of edges connecting pairs of vertices. Complex networks are modelled as random graphs, where the vertices and the edges are chosen randomly, according to an appropriate probability distribution. Search algorithms, in turn, are modelled as random walks, which move along the network by randomly picking an edge incident to the vertex that is currently visited and jumping to the vertex at the other end. 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. One of the key motivations is that it gives information about the geometry of the graph.

Many real-world networks are dynamic in nature. It is therefore natural to study random walks on dynamic random graphs. In this talk we focuson one particular example, namely, a random graph with prescribed degrees (also called the configuration model). 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.

Joint work with Luca Avena, Hakan Guldas and Remco van der Hofstad.

Coffee will be served between the lectures

Drinks will be served after the lecture

Venue: Lipschitz-Hall, Mathematics Centre, Endenicher Allee 60.