URL study guide
https://tue.osiris-student.nl/onderwijscatalogus/extern/cursus?cursuscode=2MMS60&collegejaar=2025&taal=enOmschrijving
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.
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.
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.
Doelstellingen
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 results in a systematic way.
The practical learning goals will be achieved through a project assignment that students will carry out throughout the quarter.
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 decompose variables as sums of indicators.
T3 Students can couple random variables to one another.
T4 Students can bound random variabes using stochastic ordering.
T5 Students can apply breadth first search algorithms to graphs.
T6 Students can identify branching processes as random walks and apply random walk theory to prove properties about branching processes.
T7 Students know how in specific cases branching processes may be used as approximations of random graph models.
T8 Students can formulate the Erdös-Rényi (ER) model and prove its basic properties using techniques in T1-T7.
T9 Students can identify and prove a “phase transition” of the ER model and apply this phase transition to prove further properties of ER models.
T10 Students can formulate the Generalized Random Graph (GRG) model and compute propabilities of small instances of this model.
T11 Students can compute empirical distributions (arising from both deterministic and random sequences) and can find their limits.
T12 Students can identify and prove properties of the degree structure of GRG models.
T13 Students can formulate the Configuration Model (CM) and compute probabilities of small instances of this model.
T14 Students can compute simplicity probability of the CM.
T15 Students know which branching processes can be used to approximate the CM.
T16 Students can identify and “phase transition” in the CM.
T17 Students can formulate the preferential attachment model (PA) and compute probabilities of simple instances of this model.
T18 Students know what power laws are and how they come into play in the PA model.
T19 Students can identify convergence of the degree sequence of PA models.
T20 Students know about possible other random graph models that extend the models in T8, T10, T13 and T17,
The theoretical learning goals will be achieved through lectures (to lean about the theory) and subsequent instructions (to practice the theory and techniques). A tentative planning of the learning goals is as follows:
Preliminaries – 1 week (T1-T4).
Branching processes and random walks – ½ week (T5, T6)
Erdös-Renyi model – 2 weeks (T7-T9)
Generalized random graph model – ½ week (T10-T12)
Cofiguration model – 1½ weeks (T11, T13-16)
Preferential attachment model – 1½ weeks (T17-T19)
Model extensions and properties – ½ week (T20)
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 results in a systematic way.
The practical learning goals will be achieved through a project assignment that students will carry out throughout the quarter.
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 decompose variables as sums of indicators.
T3 Students can couple random variables to one another.
T4 Students can bound random variabes using stochastic ordering.
T5 Students can apply breadth first search algorithms to graphs.
T6 Students can identify branching processes as random walks and apply random walk theory to prove properties about branching processes.
T7 Students know how in specific cases branching processes may be used as approximations of random graph models.
T8 Students can formulate the Erdös-Rényi (ER) model and prove its basic properties using techniques in T1-T7.
T9 Students can identify and prove a “phase transition” of the ER model and apply this phase transition to prove further properties of ER models.
T10 Students can formulate the Generalized Random Graph (GRG) model and compute propabilities of small instances of this model.
T11 Students can compute empirical distributions (arising from both deterministic and random sequences) and can find their limits.
T12 Students can identify and prove properties of the degree structure of GRG models.
T13 Students can formulate the Configuration Model (CM) and compute probabilities of small instances of this model.
T14 Students can compute simplicity probability of the CM.
T15 Students know which branching processes can be used to approximate the CM.
T16 Students can identify and “phase transition” in the CM.
T17 Students can formulate the preferential attachment model (PA) and compute probabilities of simple instances of this model.
T18 Students know what power laws are and how they come into play in the PA model.
T19 Students can identify convergence of the degree sequence of PA models.
T20 Students know about possible other random graph models that extend the models in T8, T10, T13 and T17,
The theoretical learning goals will be achieved through lectures (to lean about the theory) and subsequent instructions (to practice the theory and techniques). A tentative planning of the learning goals is as follows:
Preliminaries – 1 week (T1-T4).
Branching processes and random walks – ½ week (T5, T6)
Erdös-Renyi model – 2 weeks (T7-T9)
Generalized random graph model – ½ week (T10-T12)
Cofiguration model – 1½ weeks (T11, T13-16)
Preferential attachment model – 1½ weeks (T17-T19)
Model extensions and properties – ½ week (T20)