Structure and dynamics of complex networks
Course Status: Mandatory
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
By the end of this course, 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;
- understand the current literature in the field of complex networks.
(1) Assessment 1 (20%) Homework
(2) Assessment 2 (30%) Midterm test
(3) Assessment 3 (45%) Project work
Elements of calculus, differential equations.