Entrance hall of the ICMS

MIGSAA Special Course on Random Graphs and their Applications

Apr 10, 2017 - Apr 13, 2017

ICMS

 

Invited Lecturers

Remco van der Hofstad (Technical University of Eindhoven)

Justin Salez (Universite Paris Diderot)

 

Organisers 

Sergey Foss (Heriot-Watt University)

Seva Shneer (Heriot-Watt University)

 


 

Arrangements

This event will be held at ICMS.  ICMS is located at 15 South College Street, Edinburgh, EH8 9AA

 

21/02/17 - the organisers have arranged for further spaces to be made available.  To apply for one of the remaining spaces, please complete the application form.

 

 

Programme

A preliminary programme (same for all 4 days of the school) is planned:

 

09:00-10:30 - lecture by Remco van der Hofstad

10:30-11:00 - coffee break

11:00-12:00 - lecture by Remco van der Hofstad

12:00-13:30 - lunch

13:30-14:30 - lecture by Justin Salez

14:30-15:00 - coffee break

15:00-16:00 - lecture by Justin Salez

 

 

Preliminary programme

1. Complex networks and random graphs: structure and functionality (Remco van der Hofstad)

Empirical findings have shown that many real-world networks share fascinating features. Indeed, many real-world networks are small worlds, in the sense that typical distances are much smaller than the size of the network. Further, many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks. Therefore, such networks are highly inhomogeneous.

Spurred by these empirical findings, models have been proposed for such networks. In this lecture series, we discuss empirical findings of real-world networks, and describe some of the random graph models proposed for them. In particular, we will discuss the configuration model, generalized random graphs and preferential attachment models. We then discuss topological features of these models, such as the small-world phenomenon in these random graph models and its link to `six degrees of separation'. We highlight some of the ingredients used in the proofs, namely the tree-like nature of the random graphs under consideration and the use of branching processes.

Further, we explain that we can think of the functionality of real-world networks as stochastic processes acting on them, leading to double randomness of stochastic processes on random graphs. Examples of such stochastic processes include information diffusion on networks, competition between different species exploring a network and the resilience of networks under attack.

A rough outline of the lecture series is as follows:

  • Lectures 1-2 (three hours): Real-world networks, random graph models and their small-world structure
  • Lectures 3-4 (three hours): Stochastic processes on random graphs: percolation and resilience
  • Lectures 5-6 (three hours): Stochastic processes on random graphs: information diffusion and epidemics
  • Lectures 7-8 (three hours): Stochastic processes on random graphs: competition and consensus formation

This lecture series is based on the book by Prof vd Hofstad (volume I is ready and volume II is in preparation, notes may be found at http://www.win.tue.nl/~rhofstad/) and well as on joint work with:Gerard Hooghiemstra, Shankar Bhamidi, Juli Komjathy, Enrico Baroni, Mia Deijfen, Piet Van Mieghem, Henri van den Esker and Dmitri Znamenski.

 

2. Mixing time and cutoff for random walks on random graphs (Justin Salez)

The time it takes for a random walk to converge to equilibrium on a graph is a gauge for an array of properties of the underlying geometry: distances between vertices, local traps, global bottlenecks, isoperimetric profile, expansion, etc. It also plays an essential role in real-world-network applications, such as exploration and ranking in the World Wide Web. In recent years, the understanding of large random graphs has become sufficiently developed to allow for a detailed analysis of their mixing time, and a rigorous proof of the celebrated cutoff phenomenon. The aim of this 4-hour lecture is to describe these results in details on a few simple models. Applications to linked-based ranking algorithms in large relational databases will also be discussed.

The first two hours will consist of a a self-contained introduction ot Markov chain mixing and the the cutoff phenomenon.  The next two will be specifically devoted to the case of random walks on random graphs.


3. Local weak limits of random graphs and applications (Justin Salez)

In the sparse regime (where the numbers of edges and vertices tend to infinity in a comparable way), the asymptotic behaviour of many graph parameters happens to be essentially determined by the local geometry around a typical vertex only. One way to formalise this is to establish the continuity of the observables of interest with respect to the topology of local weak convergence. This approach allows one to replace the asymptotic study of large complex networks by the direct analysis of simple limiting structures such as Galton-Watson trees, on which explicit formulae can often be easily obtained. The 4-hour lecture is an introduction to this powerful method, illustrated by a few classical examples of graph parameters arising from combinatorial optimization or statistical mechanics. Applications to popular local message-passing algorithms such as Belief Propagation will also be discussed.

The first two hours will consist of a a self-contained introduction to the framework of local weak convergence.  The next two will illustrate these general principles with two detailed applications.

 

 

Participants

Name Institution
Abla, Azalekor Heriot-Watt university
Almutlg, Ahmad Heriot-Watt University
Bhattacharjee, Arnab Heriot-Watt University
Buke, Burak University of Edinburgh
Cheek, David MIGSAA
Cruise, James Heriot-Watt University
Daly, Fraser Heriot-Watt University
Davidson, Angus University of Bristol
de Kergorlay, Henry-Louis University of Edinburgh
Dean, Justin University of Bristol
Dhara, Souvik Eindhoven University of Technology
Esmalifalak, Hamidreza Heriot Watt
Garavaglia, Alessandro Eindhoven University of Technology
Gerle, Fabian University of Duisburg-Essen
Hammersley, William MIGSAA
Hansen, Jennie Heriot-Watt University
Homer, Alexander University of Oxford
Hryniv, Ostap Durham University
Jordan, Jonathan University of Sheffield
Kreiss, Alexander Heidelberg University
Lelli, Andrea University of Bath
McRedmond, James Durham University
Mollison, Denis Heriot-Watt University
Moraki, Eleni MIGSAA
Nanxin, Wei Imperial College London
Nicholson, Michael University of Edinburgh
Prasolov, Timofei Heriot-Watt University
Reichmann, Lena Mannheim University
Ritter, Daniel Ludwig-Maximilians-Universität München
Rivera, Nicolás King's College London
Rojas, Geronimo Univeristät Duisburg-Essen
Samantha, Ahern UCL
Schmuck, Markus Heriot-Watt University
stegehuis, clara TU Eindhoven
Tan, Shuren University of Edinburgh
Tanner, Nora MIGSAA
Toh, Bemsibom Heriot-Watt University
Wade, Andrew Durham University
Yarrow, Mark University of Sheffield
Zhang, Ying MIGSAA