AMML 2024-2025 by Pietro Caputo. Public Lecture/Navigating Networks by Random Walks

Ashok Maitra Memorial Lectures 2024-25
Professor Pietro Caputo
www.isibang.ac...
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.