Skip to main content

Unit information: Complex Networks 4 in 2015/16

Please note: you are viewing unit and programme information for a past academic year. Please see the current academic year for up to date information.

Unit name Complex Networks 4
Unit code MATHM6201
Credit points 20
Level of study M/7
Teaching block(s) Teaching Block 1 (weeks 1 - 12)
Unit director Dr. Ayalvadi Ganesh
Open unit status Not open

MATH11300 Probability 1 (or equivalent) and MATH 11005 Linear Algebra & Geometry (or equivalent). 



School/department School of Mathematics
Faculty Faculty of Science


Complex networks is an area of intense current research with prevalent applications in a number of domains including communication, transport and power networks, biological regulatory networks and social networks. The last two decades have seen a great deal of progress in research on the structure and properties of such networks, and on algorithms operating over networks. With the recent appointment of staff in the area of complexity, with increasing student interest in modelling and analysing these areas of application, and with the current state of the subject, now is an opportune time to offer new units in this exciting area.

The lectures for this unit will be delivered in common with those for the proposed Level 6 unit Complex Networks 3 (MATH 36201), but successful completion of this unit will require greater depth of understanding and independent learning than that required for the Level 6 unit.


Understand how to mathematically model complex networks. Learn to analyse stochastic processes on networks.


  • Rumours, epidemics and consensus on networks
  • Spectral graph theory and random walks on networks
  • Decentralised routing

Relation to Other Units

The unit introduces Markov chain models, seen in Applied Probability 2 (which is not a pre-requisite but is recommended) and applies them to the study of random processes on networks. Information Theory, Complex Networks, Financial Mathematics, and Queueing Networks, all involve the application of probability theory to problems arising in various fields.

Intended learning outcomes

  • Learn to model a variety of stochastic processes on graphs, including random walks and the spread of information and epidemics
  • Learn to analyse these processes to obtain bounds and approximations for quantities of interest
  • Learn about the relationship of graph spectra to various properties of the graph.

Transferable Skills:

The ability to develop and analyse probabilistic models for a variety of algorithms and processes on complex networks.

Teaching details

Lectures and problem sheets, from which work will be set and marked, with outline solutions handed out a fortnight later. The student will read a research article and present a summary of it.

Assessment Details

  • 70% of the final assessment mark will be based on a 2½-hour examination in April consisting of FIVE questions. A candidate's best FOUR answers will be used for assessment. Candidates are allowed to bring a single A4-sized double-sided sheet of notes into the examination. Calculators are not allowed.
  • 15% of the mark will be based on solutions handed in to set homework problems.
  • 15% of the mark will be based on a presentation given by the student. The presentation will be a review of a suitable research paper.

Reading and References

Readings will primarily be from journal articles and lecture notes. However, some books that contain relevant material are:

  • M. Draief and L. Massoulie, "Epidemics and Rumours in Complex Networks", LMS Lecture Note Series 369, Cambridge University Press, 2009.
  • D. Shah, "Gossip Algorithms", NOW Publishers Inc., 2009.