# Random Graph and Network Simulations

**RANDOM GRAPHS AND NETWORK SIMULATIONS SYLLABUS**

**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:**

*Introduction*

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.

**Assessment:**

- 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.**