Breadcrumb

Complex Networks 3 (MATH 36201)

Academic Year:

Contents of this document:

Administrative Information

  1. Unit number and title: MATH 36201 Complex Networks 3
  2. Level: H/6
  3. Credit point value: 20 credit points
  4. Year: 12/13
  5. First Given in this form: 2009
  6. Unit Organiser: Ayalvadi Ganesh
  7. Lecturer: Ayalvadi Ganesh
  8. Teaching block: 1
  9. Prerequisites: MATH11300 Probability 1 (or equivalent) and MATH 11005 Linear Algebra & Geometry (or equivalent).

Unit aims

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

General Description of the Unit

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: Markov chains in discrete and continuous time
  • Spread of information and epidemics on networks
  • Voter model and consensus on networks
  • Random walks on networks and spectral graph theory

Relation to Other Units

The unit introduces Markov chain models seen in Applied Probability 2 (which is not a pre-requisite but is desirable) 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.

Teaching Methods

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

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

 

Assessment Methods

The final assessment mark for Complex Networks 3 is 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.

Award of Credit Points

Credit points are gained by:

  • either passing the unit (with a final assessment mark of 40 or higher)
  • or getting a final assessment mark of 30 or higher including a pass (mark of 40 or higher) on the project.

Transferable Skills

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

Texts

Readings will primarily be from 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.

Syllabus

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