Random Graph and Network Simulations

Course Description: 


Level: Doctoral
Course Status: Elective

Full description: 

Background and overall aim of the course:

The success of the new science of networks is partly due to the realization of universal features in a wide range of applications,  but also due to very successful simple models. The following questions will be discussed: How to identify the relevance of some properties of a network? How to construct adequate reference systems? How to modify basic models to improve agreement with empirical observations? What are the typical processes on random networks? How to write efficient programs to simulate networks and processes on them?

The course covers the simplest random network model (the Erdös-Rényi graph), the configuration model, and tailored random graph models. We will deal with the Watts-Strogatz small world model, the Barabási-Albert preferential attachment model and its modifications, with geographical scale free models. We will also discuss diffusion and spreading on complex networks.

This course builds to some extent on “Fundamental ideas in network science” and it focuses on improving skills so that students can actively apply the concepts.

The learning outcomes of the course.

By successfully absolving the course the students will be able to:

- Use simple networks to model empirical observations;

- Model dynamic processes on complex networks;

- Define appropriate reference systems to validate or disprove network hypotheses

- Write programs for random graphs and processes on them

Planned weekly schedule:

Week                                                      Comments

1        Introduction                           

2        Erdös-Rényi graph      

3        Configuration model

4        Tailoring random graph models               

5        Small world model                                

6        Power law degree distribution             Assignment

7        Mesosopic structures                         Handing out the projects

8        Weighted network models

9        Diffusion and spreading on networks

10      Bursty signals and temporal networks 

11      Multi agent modeling                          Assignment

12      Project presentation


Detailed description:


Understanding our complex world. Complex networks are everywhere: examples. Graph properties and measures. Universal features.


Erdős-Rényi graphs

The definition of the ER model. Ensemble of graphs. Percolation transition in the ER model. Degree distribution, clustering, average path length. Distribution of finite clusters. Limitation of the applicability.


Configuration model

Random graph model with arbitrary degree distribution. The configuration model as a standard null model. Properties. Directed configuration model.


Tailoring random graphs

Generalized configuration models. Exponential random graphs (p* models).  Network optimization.


Small world model

Watts-Strogatz model: rewiring and adding shortcuts. Calculation of the shortest path, degree distribution and clustering coefficient. Scaling.


Power law degree distribution

Barabási-Albert model. Temporal evolution. Degree distribution. Clustering coefficient. Small and ultrasmall worlds. Vertex copying models. Geographical models.


Mesoscopic structures

Motifs and their calculation. Communities. Basic detection methods. Benchmarks.


Weighted network models

Different sources of weights. Intensity and coherence. Weighted motifs and communities.


Diffusion and spreading on networks

The diffusion problem. Diffusion on the ER, WS, BA graphs. Basic epidemic spreading models. Mean field solutions. The models on graphs.


Bursty signals and temporal networks

Burstiness as basic feature of human behavior. Communication networks are temporal. Characterization. Temporal motifs.


Multi agent modeling

Heterogeneous interacting agents. Topological constrains – network aspects. Calibration.


- Assignments (30%)

- Modeling task (30%)

- Final project (carried out in pairs) (30%)

- Teacher evaluation (10%)

Such further items as the course website (e-learning site), assessment deadlines, office hours, contact details etc. Details will be given during the course.