Random Graph and Network Simulations
RANDOM GRAPHS AND NETWORK SIMULATIONS SYLLABUS
Course Status: Elective
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:
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
Understanding our complex world. Complex networks are everywhere: examples. Graph properties and measures. Universal features.
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.
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.
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.