Complex Networks 3

Unit aims

Understand how to mathematically model complex networks. Learn to analyse stochastic processes such as rumour spread, epidemics and consensus on networks.

Unit description

This unit will teach ways of modelling and working with large complex networks such as the Internet and social networks.   The topics covered will be

• Probability background: Continuous time Markov chains and Poisson processes
• Spread of information and epidemics on networks
• Consensus models on networks
• Random walks on networks and spectral graph theory
• Random graphs

Relation to other units

The unit extends Markov chain models seen in Probability 2 to continuous time, 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.

Probability 2 is a pre-requisite for this course. Students from other departments who have not taken it should discuss the suitability of this course with the unit organiser before registering for it.

Learning objectives

• 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

Learn about probabilistic models such as Markov chains and martingales. Develop the ability to apply them in the context of stochastic processes on complex networks.

Syllabus

• Markov chains in continuous time
• Poisson process
• Rumours, epidemics and consensus on networks
• Spectral graph theory
• Random walks on networks
• Random graph models.

Students will be provided with comprehensive lecture notes.  In addition, 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.

R. Durrett, "Random Graph Dynamics", Cambridge University Press, 2007.

Unit code: MATH36201
Level of study: H/6
Credit points: 20
Teaching block (weeks): 1 (1-12)

Pre-requisites

MATH11005 Linear Algebra and Geometry (or equivalent) and MATH20008 Probability 2 (or equivalent).

None

Methods of teaching

Lectures and problem sheets, from which work will be set and marked, with outline solutions handed out a fortnight later.

Methods of Assessment

The pass mark for this unit is 40.

The final mark is calculated as follows:

• 100% from a 2 hour 30 minute exam

NOTE: Calculators are NOT allowed in the examination.

For information resit arrangements, please see the re-sit page on the intranet.

Please use these links for further information on relative weighting and marking criteria.

Further exam information can be found on the Maths Intranet.