Our colloquium usually takes place on the first Tuesday of each month from 15:30 to 16:30 in room A709. A renowned expert (being an excellent speaker as well) visits us for an afternoon and gives a panorama of one of her research areas. The talk is meant to be accessible to all members of the lab, including PhD students in analysis, game theory, probability and statistics. Food and drinks are served after the event!
Date: Tuesday, December 5th 2023 (15:30-16:30, room C206)
Title: Navigating Networks by Random Walks
Abstract: In the analysis of a large, complex network, exploration via random walks is often the most effective strategy available. How long does it take to traverse the entire network ? Does the walk achieve a stable equilibrium, and if so, how long is the journey to reach it ? And crucially, what does this steady state look like ? The answers to these questions are key to understanding a network's structural features and provide valuable insights for ranking systems and search algorithms. Developing a comprehensive mathematical treatment of these issues for real-world networks poses a formidable task, and a rigorous analysis has only recently started in the context of relatively simple models. In this lecture, we illustrate some promising preliminary progress in the setting of directed networks obtained from simple random graph models. The discussion includes scenarios where the walker experiences regeneration events such as teleportation, as in PageRank algorithms, or resampling of the underlying graph, as in a dynamically evolving network.