Complex Networks


Ayalvadi Ganesh (

Office hours: Mondays, 10-12. Room 1.40, Fry Building.


There is no set text but lecture notes will be provided online covering the course material. Additional reading, covering some of the course material in greater depth or from different perspectives can be found in:

Moez Draief and Laurent Massoulie, Epidemics and Rumours in Complex Networks, Cambridge University Press, 2009.

Devavrat Shah, Gossip Algorithms, NOW Publishers Inc., 2009.

Remco van der Hofstad’s Lecture Notes, available online.

Homework policy: Homework is an important part of learning the material on this course and you are strongly encouraged to attempt all the homework problems. It can be helpful to work together with others on homework problems, and this is encouraged, but it is good practice to write out the solutions on your own.

For those taking the course at Level H/6, you will need to complete two items of assessed coursework, which will count for 20% of your final mark.

Presentations: For those taking the course at Level M/7, you are required to read a research paper and make a brief presentation about it. This will count for 16% of your final mark and peer marking of a small number of other presentations for 4%.

You may choose from a list of suggested papers below, or another paper of your choice relevant to the course but discuss it with me first.

Suggested Papers for Presentations

The presentations will be marked according to the following Marking Criteria.

Lecture videos

Lectures will be in-person. In addition, recorded lecture videos are available here. These may not map 1-1 to the in-person lectures.

Lecture notes

Markov chains

Rumour spreading


Graphs and Matrices

Random Walks

Random graphs

Homework problems

Problem Sheet 1                                              Solutions

Problem Sheet 2                                              Solutions

Problem Sheet 3          Due 20 Oct                 Solutions

Problem Sheet 4                                              Solutions

Problem Sheet 5          Due 13 Nov                Solutions

Problem Sheet 6          Due 24 Nov                Solutions

Problem Sheet 7          Due 8 Dec                   Solutions

Problem Sheet 8                                              Solutions