Course Description

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?

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 discuss the theory of diffusion and of 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.

COURSE SCHEDULE

Week Description

Comment

1 Introduction

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

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

3 Configuration model

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

4 Tailoring random graphs

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

5 Small world model

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

6 Power law degree distribution

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

7 Mesoscopic structures

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

Midterm test

8 Weighted network models

Different sources of weights. Min cut max flow theorem. Intensity and coherence. Weighted motifs and communities.

9 Diffusion and spreading on networks

The diffusion problem. Diffusion on the ER, WS, BA graphs. Stationary solutions, relaxation. Searching on networks.

10 Basic epidemic spreading models. Threshold phenomena. Mean field solutions. Epidemic models on graphs. The dynamics of spreading.

11 Bursty signals and temporal networks

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

12 Project presentation

Reading

M.E.J. Newman: Networks. An introduction (Oxford UP, 2010)

A. Barrat, M. Barthélemy and A. Vespignani: Dynamic Processes on Networks (Cambridge, 2008)

Pre-requisites: Basic programming skills, basic calculus and differential equations.It is advisable to take this course after “Fundamental ideas in network science”.

Course e-learning site: http://e-learning.ceu.hu/course/view.php?id=1727

Office hours: upon agreement