Random Graphs
Course:
Course types
Course
Information
Time Period
01/09/2015 – 31/08/2027Format
CourseInstruction Language
EnglishCourse Credits
ECTSManaging Organisation
About
In this course, the students get acquainted with the most popular (large) random graph models of real complex networks and their basic properties. The course starts with the classical random graphs first studied by Erdös and Rényi. In this random graph model, we start with the complete graph on n vertices, and erase edges independently with probability 1-p, where p is the parameter of the model. We will study the phase transition for the largest connected component, taking place at p=1/n, where the largest connected component suddenly grows from a logarithmic size to a size proportional to the volume of the graph. This provides the simplest model that exhibits phase transition.
After the discussion of the classical Erdös and Rényi random graph, we will discuss more recent random graph models, which have been invented to model real-life complex networks. Complex networks are large networks, such as the networks describing the relations in a large population (such as online social networks, e.g. Facebook or Twitter), the internet network, or traffic networks. In experiments, it has been discovered that such complex networks behave rather differently from the classical Erdös and Rényi random graph, and this is due to the large inhomogeneity in the degrees of vertices. Of these modern complex network models, we will study basic properties of these networks such as the degree structure.
We end the course by highlighting some modern theoretical techniques in random graph theory and how these relate to the models and results already obtained. In parallel to the lectures, all students will work on a modelling project where they will explore questions about real-life applications or modern random graph models through simulations. They will give them hands-on experience working with (data from) random graphs in practice.
After the discussion of the classical Erdös and Rényi random graph, we will discuss more recent random graph models, which have been invented to model real-life complex networks. Complex networks are large networks, such as the networks describing the relations in a large population (such as online social networks, e.g. Facebook or Twitter), the internet network, or traffic networks. In experiments, it has been discovered that such complex networks behave rather differently from the classical Erdös and Rényi random graph, and this is due to the large inhomogeneity in the degrees of vertices. Of these modern complex network models, we will study basic properties of these networks such as the degree structure.
We end the course by highlighting some modern theoretical techniques in random graph theory and how these relate to the models and results already obtained. In parallel to the lectures, all students will work on a modelling project where they will explore questions about real-life applications or modern random graph models through simulations. They will give them hands-on experience working with (data from) random graphs in practice.
Objectives
During the course students will be introduced to various random graph models to model real life networks. They will be equipped with both mathematical and programming techniques to derive properties about random graphs in both a theoretical and practical setting.
For the practical facet of the course (30% in the final assessment) the learning goals include:
P1 Students can implement formulation of random graphs models in a programming language of their choosing.
P2 Students can design experiments to investigate (predescribed) properties of the implemented model.
P3 Students can find and implement algorithms to analyse random graphs.
P4 Students can use these analyses to formulate theoretical conjectures about a random graph model.
P5 Students can document their methodology and results in a systematic way.
For the theoretical facet of the course (70% in the final assessment) the learning goals include:
T1 Students know the definition of different way random variables can converge and can prove this in various settings.
T2 Students can couple random variables to one another.
T3 Students can bound random variabes using stochastic ordering.
T4 Students can identify branching processes as random walks and apply random walk theory to prove properties about branching processes.
T5 Students know how in specific cases branching processes may be used as approximations of random graph models.
T6 Students can identify and prove a “phase transition” of the ER model and apply this phase transition to prove further properties of ER models.
T7 Students can compute empirical distributions (arising from both deterministic and random sequences) and can find their limits.
T8 Students can formulate the Configuration Model (CM) and compute probabilities of small instances of this model.
T9 Students can compute simplicity probability of the CM.
T10 Students know which branching processes can be used to approximate the CM.
T11 Students can identify and “phase transition” in the CM.
T12 Students can formulate the preferential attachment model (PA) and compute probabilities of simple instances of this model.
T13 Students know what power laws are and how they come into play in the PA model.
T14 Students know what local convergence of deterministic graphs is and can apply it to simple examples.
T15 Students know how local convergence extends to random graphs and can relate it to phase transition proofs.
(T16 Students can use random graph models to prove combinatoric properties of graphs)
A tentative planning of the course is as follows:
Preliminaries – 1 week (T1-T3).
Branching processes and Erdös-Renyi model – 1½ weeks (T4-T6)
Cofiguration model – 2 weeks (T7-T11)
Preferential attachment model – 1 week (T12, T13)
Local convergence – 1½ week (T14, T15)
For the practical facet of the course (30% in the final assessment) the learning goals include:
P1 Students can implement formulation of random graphs models in a programming language of their choosing.
P2 Students can design experiments to investigate (predescribed) properties of the implemented model.
P3 Students can find and implement algorithms to analyse random graphs.
P4 Students can use these analyses to formulate theoretical conjectures about a random graph model.
P5 Students can document their methodology and results in a systematic way.
For the theoretical facet of the course (70% in the final assessment) the learning goals include:
T1 Students know the definition of different way random variables can converge and can prove this in various settings.
T2 Students can couple random variables to one another.
T3 Students can bound random variabes using stochastic ordering.
T4 Students can identify branching processes as random walks and apply random walk theory to prove properties about branching processes.
T5 Students know how in specific cases branching processes may be used as approximations of random graph models.
T6 Students can identify and prove a “phase transition” of the ER model and apply this phase transition to prove further properties of ER models.
T7 Students can compute empirical distributions (arising from both deterministic and random sequences) and can find their limits.
T8 Students can formulate the Configuration Model (CM) and compute probabilities of small instances of this model.
T9 Students can compute simplicity probability of the CM.
T10 Students know which branching processes can be used to approximate the CM.
T11 Students can identify and “phase transition” in the CM.
T12 Students can formulate the preferential attachment model (PA) and compute probabilities of simple instances of this model.
T13 Students know what power laws are and how they come into play in the PA model.
T14 Students know what local convergence of deterministic graphs is and can apply it to simple examples.
T15 Students know how local convergence extends to random graphs and can relate it to phase transition proofs.
(T16 Students can use random graph models to prove combinatoric properties of graphs)
A tentative planning of the course is as follows:
Preliminaries – 1 week (T1-T3).
Branching processes and Erdös-Renyi model – 1½ weeks (T4-T6)
Cofiguration model – 2 weeks (T7-T11)
Preferential attachment model – 1 week (T12, T13)
Local convergence – 1½ week (T14, T15)
Method of Assessment
Written examination