Complex Networks vs. Random Graphs

Applied Maths Honours, 1st semester 2018, Lecturer: Eduardo G. Altmann

this www:

Codes and Notebooks:

Classes: Tuesdays and Thursdays 9-10AM, AGR room

Consultation: Wednesday 9-10AM, in my office (Carslaw 615)

Assessment: Exam (50%), Assignment (25%), and Project (25%). Attendance to class is essential.
Assignment was due on Thursday April 5th (noon), marks sent by e-mail.
Project: took place on Weeks 12 and 13, choose your project in the forum from Edstem .

Abstract: The representation of the relationship (links) between objects (nodes) in form of a network is increasingly popular in social, economical, biological, and technological sciences. Real-world examples of networks coming from these various fields show striking differences to the random-graph models proposed by mathematicians (in the mid XX century). For instance, real networks show (i) a large number of triangles, short loops, and other small subgraphs which are absent in simple random-graph models; and (ii) the distribution of the number of links that nodes receive deviates from a Binomial and shows large skewness (fat-tailed distribution). The goals of this course are to characterize these disagreements between complex networks and random graphs, to show why they matter, and to present more advanced mathematical methods to model complex networks. The course will start with a general introduction to the field of complex networks, discussing different examples of networks and how to characterize them (e.g., clustering and centrality measures). We will then introduce and apply computational methods to empirically-measured networks. The main part of the course will be the definition and characterization of different random-graph ensembles. Some significant deviations between random graphs and real networks will be explored, with focus on the small-world effect, the fat-tailed degree distribution, and the consequences to network robustness. In the final part of the course we will discuss how more advanced random-graph ensembles (e.g., exponential random-graph models) can be used to characterize real-world networks. This will be interpreted in terms of – and serve as an introduction to – more general ideas and methods, such as the Principle of Maximum Entropy and Importance Sampling Monte Carlo methods (e.g., the Metropolis Algorithm). This course involves computer simulations and data analysis. Familiarity with a programming language (e.g., Python or Matlab) and basic statistical concepts are desired.

Objectives and learning outcome: develop analytical, numerical, and modeling skills that help to connect abstract mathematical ideas to real-world systems represented as networks.


Software for computation:

Network data:

Tentative week-by-week outline:

Week | Date


Computation / Homeworks

1 | 6-8/3

I - Introduction

Motivation, definitions, notation

 Visualize Networks

2 | 13-15/3

II -Network Characterization:

Local and global measures

Compute measures

3 | 20-22/3


Centrality Measures

Compute most central nodes

4 | 27-29/3

III - Network Models


Poisson Random Graphs

Generate networks





 due April 5 (noon)

5 | 10-12/4



Small World Networks

Simulate WS model

6 | 17-19/4


Scale-free networks


7 | 24-26/4


Random graphs, Maximum Entropy Principle, ERGMs

Shuffling links

8 | 1-3/5


Importance Sampling, Stochastic Block Models

Choice of Projects

9 | 8-10/5

IV – Network Resilience

Percolation and random failures


10 | 15-17/5


Targeted attacks


11 | 20-24/5

V – Dynamics on Networks

Cascades, Epidemics, etc.


12 | 29-31/5


Project Presentation

13 | 5-7/6

Project Presentation(?)


14 or 15 | ?