Breadcrumb

Complex Networks 34 (MATH M6201)

Academic Year:

Contents of this document:

Administrative Information

  1. Unit number and title: MATH M6201 Complex Networks 34
  2. Level: M/7
  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 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
  • Consensus on networks
  • Random walks on networks and introduction to 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 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.

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

80% 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.

10% of the mark will be based on solutions handed in to set homework problems.

 10% of the mark will be based on reading and presenting a research paper.

Award of Credit Points

Credit points are gained by:

  • either passing the unit (with a final assessment mark of 50 or higher),
  • or obtaining a final assessment mark of 40 of higher and handing in satisfactory answers to more than half of the set homework problems.

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

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