nl en

Probability seminar: Random Graph ensembles (BM)



The probability seminar aims at exposing students to advanced probability theory and selected applications. A different topic is selected each year. The topic for the academic year 2018-2019 is Random Graph Ensembles.

Real-world networks share fascinating features. Many are small world and scale-free. These properties have fundamental implications for both the structure and the performance of networks. Network science aims at understanding why networks have these properties, and what are the consequences both qualitatively and quantitatively.

Complex networks plays an increasingly important role in science. Examples include electrical power grids, transportation and traffic networks, telephony networks, Internet and the World-Wide Web, Facebook and Twitter, as well as collaboration and citation networks. The structure of such networks affects their performance. For instance, the topology of social networks affects the spread of information and disease, while the topology of Internet affects its success as a means of communication.

Networks are modelled as graphs, i.e., a set of vertices connected by a set of edges. A common feature of real-world networks is that they are large and complex. Consequently, a full description of their topology is impossible, which is why much research focusses on local properties: How many vertices does the network have? According to what rules are the vertices connected to one another by edges? What cluster sizes and cluster shapes are most common? What is the average distance between two vertices? What is the maximal distance between two vertices? These local properties are typically probabilistic, which leads to the study of random graphs.

In this seminar we focus on a handful of key network models. Our goal is to explain universal behaviour with the help of probabilistic techniques.


Familiarity with basic concepts in probability theory and combinatorics.


The course material is based on the following references, together with selected topical research papers
that will be made available during the course:

  • R. van der Hofstad, Random Graphs and Complex Networks, Volume 1, Cambridge University Press, 2017. Available at: Website

  • A.-L. Barabasi, Network Science. Available at: Website

  • M. Emmerich, D. Garlaschelli, F. den Hollander, Lecture Notes on Complex Networks, 2016. Available on request.

Plan and exam

Three introductory lectures and two advanced lectures will be given by Avena and den Hollander.

All the other lectures will given by the participants. Each participant gives 2 presentations:

  • one dedicated to some aspects of the general theory,

  • one chosen from a list of topics presented during the course.

For the second presentation, a short hand-out (to be distributed to all the participants) must be prepared
as well.

The final grade is based on active participation, the two presentations and the hand-out.