## 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 |
---|---|

Almutlg, Ahmad | Heriot-Watt University |

Bhattacharjee, Arnab | Heriot-Watt University |

Buke, Burak | University of Edinburgh |

Cheek, David | MIGSAA |

Cruise, James | Heriot-Watt University |

Czechon, Agnieszka | The University of Edinburgh |

Daly, Fraser | Heriot-Watt University |

de Kergorlay, Henry-Louis | MIGSAA |

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 |

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 |

Stasinski, Roman | University of Oxford |

Stegehuis, Clara | TU Eindhoven |

Tan, Shuren | University of Edinburgh |

Toh, Bemsibom | Heriot-Watt University |

Wade, Andrew | Durham University |

Yarrow, Mark | University of Sheffield |

Zachary, Stan | University of Edinburgh |

Zhang, Ying | MIGSAA |