C5.4 Networks - Material for the year 2020-2021

We have updated our Undergraduate exams guidance in preparation for the Trinity Term examinations.

Please see our new webpages dedicated to TT exams.

Prof. Renaud Lambiotte
General Prerequisites: 

Basic notions of linear algebra, probability and some computational experience. Numerical codes will be illustrated in Python in tutorials, but the student has the possibility to use the language of their choice. Relevant notions of graph theory will be reviewed.

Course Term: 
Course Lecture Information: 

16 lectures

Course Weight: 
1.00 unit(s)
Course Level: 

Assessment type:

Course Overview: 

Network Science provides generic tools to model and analyse systems in a broad range of disciplines, including biology, computer science and sociology. This course aims at providing an introduction to this interdisciplinary field of research, by integrating tools from graph theory, statistics and dynamical systems. Most of the topics to be considered are active modern research areas.

Learning Outcomes: 

Students will have developed a sound knowledge and appreciation of some of the tools, concepts, models, and computations used in the study of networks. The study of networks is predominantly a modern subject, so the students will also be expected to develop the ability to read and understand current (2010-2020) research papers in the field.

Course Synopsis: 

1. Introduction and short overview of useful mathematical concepts (2 lectures): Networks as abstractions; Renewal processes; Random walks and diffusion; Power-law distributions; Matrix algebra; Markov chains; Branching processes.

2. Basic structural properties of networks (2 lectures): Definition; Degree distribution; Measures derived from walks and paths; Clustering coefficient; Centrality Measures; Spectral properties.

3. Models of networks (2 lectures): Erdos-Rényi random graph; Configuration model; Network motifs; Growing network with preferential attachment.

4. Community detection (2 lectures): Newman-Girvan Modularity; Spectral optimization of modularity; Greedy optimization of modularity.

5. Dynamics, time-scales and Communities (2 lectures): Consensus dynamics; Timescale
separation in dynamical systems and networks; Dynamically invariant subspaces and externally equitable partitions

6. Dynamics I: Random walks (2 lectures): Discrete-time random walks on networks; PageRank; Mean first-passage and recurrence times; Respondent-driven sampling; Continous-Time Random Walks

7. Random walks to reveal network structure (2 lectures): Markov stability; Infomap; Walktrap; Core–periphery structure; Similarity measures and kernels

8. Dynamics II: Epidemic processes (2 lectures): Models of epidemic processes; Mean-Field Theories and Pair Approximations

Reading List: 

Self-contained lecture notes will be made available at the end of Michaelmas.