Lecturer: Robert MacKay
TAs: Emma Southall (weeks 1-5), Kutlwano Bashe (weeks 6-10)
The module runs in term 1.
Lectures: Thursdays 10-12, Fridays 10-11
Classes: Fridays 11-12
We will hold Thursdays online via MA933 Teams, and Fridays in weeks 1&2. We will endeavour to hold Fridays in person in D1.07 starting week 3, but Emma will join online and it will be available online to all as backup. UPDATE: Fri 23&30 October and 11 December will be online only.
Assessment deadlines (noon via email to me): Sheet 1 26 Oct; Sheet 2 23 Nov; Sheet 3 18 Dec. Online test 15 Jan 09.00 (UK time), deadline 16 Jan 09.00 (UK time).
For the procedure for the class test, see this page.
The assessments count 6 2/3% each and the class test 80%. 2019 class test
Below is last year’s information for reference. Following the declared module aims, I will place less emphasis on stochastic processes and more emphasis on networks than last year. In my opinion, the module could be better titled “Stochastic processes and complex networks”. But Stefan’s notes and handouts are valuable additional material.
I won't cover Spatial network models (sec. 9 of the syllabus). Nor will I say much about Martingales. Instead I will amplify on 6. Basic network definitions and statistics, to include counting cycles and to introduce node-importance quantifiers and community-detection and network aggregation methods. I will also give more on random graph models (section 8), notably exponential random graphs. Thus, spatial network models and martingales will be non-examinable, but counting cycles, node importance quantifiers, community detection, network aggregation, and exponential random graphs will be examinable. Also, in contrast to last year, probability generating functions and branching processes are examinable this year. If there is time, I'll say something about using networks to represent probability distributions and about Gibbsian processes, but it will be non-examinable.
Robert MacKay (updated 3 Dec 2020)
No lectures next week (28.11. and 29.11.) due to strike action.
Class takes place Wednesday 27.11., 10-11 in D1.07!
See calendar for up to date timetable.
Lectures: Thu 11-1 and Fri 11-12 in D1.07
Classes: Fri 12-1 in D1.07
- list of exam topics UPDATED 7.12.!
- Written class test (about 3 hours) on Friday January 17 (week 2 of term 2), 10-1pm in D1.07, counts 80/100.
No books allowed, please only come with writing material and have your student ID number ready to put on the exam booklet.
Previous class tests (ONLY 2 HOURS) from 2014 (pdf), 2015 (pdf), 2016 (pdf), 2017 (pdf) and 2018 (pdf)
- homework counts 20/100 marks
- course notes (last updated 04.12.): notes_ma933_19.pdf
- final version of course notes from last year: notes_ma933_18.pdf
- the first part of notes for the former module CO905 Stochastic models of complex systems provide a slightly more complete introduction to Markov chains and might be useful for background reading
sheet 1: due Friday 18.10., 12pm noon
Random walk, Pólya urn models, generator matrices
- sheet 2: due Friday 15.11., 12pm noon
Kingman's coalescent, Ornstein-Uhlenbeck process, Moran model, birth-death chains
- sheet 3: due Friday 17.1., 12pm noon
Geometric Brownian motion, Barabasi-Albert model, Erdos Renyi random graphs, contact process
CHANGES 6.12.: Q3.5 is not for credit! Total mark for sheet changed to 50.
18.12.: Q3(a) and (b) have been clarified in the online version, please have a look.
- hand-out 1: linear algebra
- hand-out 2: characteristic functions, Gaussian, LLN, CLT
- hand-out 3: Poisson processes
- hand-out 4: Random sequential update, Gillespie algorithm
hand-out 5: Generating functions, branching processesNOT EXAMINABLE
- hand-out 6: Heavy tails, extreme value statistics, see also extremes.ipynb for illustrations
For class material see Emma's Github page
Moran model on sheet 2: moran_model.ipynb
Python is far too slow for this kind of simulation. You can use contact.c on the SCRTP machines you have access to (for machine names see slides for week 2 on this page by Dave Quigley).
Compile the code on the command line with: gcc -lgsl -lgslcblas -O9 -ooutputname contact.c
then type in command line: nohup ./outputname &
in the same directory, the nohup in front will cause the programme to finish even if you log out (no-hangup).
Adapt the code using a text editor and recompile, should be obvious which changes to make for (a), for (b) you will have to introduce a test function to stop the code when the absorbing state is reached.
For up to 500 realizations codes only run a few minutes which is fine. If you run longer jobs, you HAVE to follow these instructions how to use 'nice', also good to find which other machines are online.
- very useful tutorial slides on Fundamentals of Heavy Tails by J. Nair, A. Wierman and B. Zwart
- tutorial on stochastic matrices including the google matrix and pagerank algorithm by D. Margalit and J. Rabinoff
- review papers on complex networks:
Complex networks: Structure and dynamics (Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U.; Physics Reports 424 (4-5), 175-308, 2006)
The Structure and Function of Complex Networks (M.E.J. Newman; SIAM Review 45(2), 167–256, 2003)