Topic outline
- Module Content
- IMPORTANT Module Information
- Assessment Information
- Online Reading List
- Q-Review
- Early feedback questionnaire
-
Announcements
Collapse all Expand all
-
Module Announcements Forum
-
Student Forum
-
-
Week 1 : Introduction
-
WEEK 1 ACTIVITIES
- Participate in the lectures.
- Read Sections 1.1 - 1.3 of Chapter 1 in the typeset Lecture notes.
WEEK 1 LECTURES AND TUTORIAL
- Lecture 1: Introduction to Complex Networks
- Lecture 2: Types of networks and their representation with edgelists and adjacency matrices. See chapter 1 Sec. 1.1-1.3 (with exception of paragraph 1.3.4)
- Tutorial: (No tutorial in week 1)
HANDWRITTEN NOTES AND SLIDES (will be avaible after the live sessions)
-
WEEK 1 Lecture 1 File
6.2MB
-
WEEK 1 Lecture 2 File
2.7MB
-
-
Week 2 : Representing graphs
-
WEEK 2 ACTIVITIES
- Participate in the lectures and tutorial
- Read Section 1.4 Chapter 1 and Sections 2.1-2.3 Chapter 2 in the typeset Lecture notes.
- Attempt the questions from the Formative Assignment 1. These will be discussed in the tutorial.
- Start working on the Assessed Coursework-Quiz 1 on the material of week 1-2. This is a summative assessment (in the form of a QMPLUS quiz) that counts 4% towards your module mark. The quiz opens on Friday, 2nd February 6pm and closes on Wednesday, 7th February 5pm. You have only one attempt at the assessment. If your attempt at the quiz is still in progress at the end of the allowed time, the answers you have filled in so far will be automatically submitted. You should read the information about assessed coursework before attempting this assessment.
WEEK 2 LECTURES AND TUTORIAL
- Lecture 1: Adjacency matrices and edgelists. See chapter 1 sec. 1-4. Bipartite networks, Network size, total number of links, Degree. See chapter 1 sec. 1.5 and chapter 2 Sec. 2.1-2.3
- Lecture 2: In and out-degree, degree distributions. See chapter 2 Paragraphs 2.3
- Tutorial: CoveringFormative Assignment 1.
HANDWRITTEN NOTES (will be avaible after the live sessions)
-
WEEK 2 Lecture 1 File
3.6MB
-
WEEK 2 Lecture 2 File
1.7MB
-
WEEK 2 Tutorial File
1.5MB
-
Formative Assignment 1 File
93.3KB
-
Solutions to Formative Assignment 1 File
95.9KB
-
ASSESSED COURSEWORK 1 (QUIZ)
-
-
Week 3 : Basic measures
-
WEEK 3 ACTIVITIES
- Participatein thelectures and tutorials
- Read Sections 2.4-2.7 Chapter 2 in the typeset Lecture notes.
- Attempt the questions from the Formative Assignment 2. These will be discussed in the tutorial.
- Complete and submit the Assessed Coursework-Quiz 1 on the material of weeks 1-2 by Wednesday, 7thFebruary 5pm. This is a summative assessment (in the form of a QMPLUS quiz) that counts 4% towards your module mark. You have only one attempt at the assessment. If your attempt at the quiz is still in progress at the end of the allowed time, the answers you have filled in so far will be automatically submitted. You should read the information about assessed coursework before attempting this assessment.
WEEK 3 LECTURES AND TUTORIAL
- Lecture 1: Paths. See chapter 2 Sec. 2.4. Shortest paths, network diameter and average distance. See chapter 2 Sec. 2.5.
- Lecture 2: Connected components. See chapter 2 Sec. 2.6 and 2.7.
- Tutorial: Covering Formative Assignment 2.
HANDWRITTEN NOTES (will be avaible after the live sessions)
- Participatein thelectures and tutorials
-
WEEK 3 Lecture 1 File
3.1MB
-
WEEK 3 Lecture 2 File
2.8MB
-
WEEK 3 Tutorial File
1.5MB
-
Formative Assignment 2 File
771.6KB
-
Solutions to Formative Assignment 2 File
787.9KB
-
-
Module Description
A graph models a set of objects and connections between them. A complex network is a graph which describes a specific conmplex system via the graph of interactions between its components. In recent times, complex networks have become an important tool for understanding systems in areas as varied as economics, biology, medicine and computer science.
The module covers mathematical ways of describing networks and analysing their structure (for example quantitative measures of how richly connected a network is). We will also study the properties of networks generated by various random models of complex networks. It also discusses applications to real systems, such as the Internet, social networks and the nervous system of the C. elegans roundworm.
The module Algorithmic Graph Theory also involves the theory of graphs but from a more pure perspective, and students will find interesting parallels between these modules.
-
Week 4 : Centrality measures
-
WEEK 4 ACTIVITIES
- Participate in the lectures and tutorial
- Read all sections of Chapter 3 in the typeset Lecture notes.
- Attemptthe questions from the Formative Assignment 3. These will be discussed in the tutorial.
- Start working on the Assessed Coursework-Quiz 2 on the material of weeks 3-4 . This is a summative assessment (in the form of a QMPLUS quiz) that counts 4% towards your module mark. The quiz opens on Friday, 16th February 6pm and closes on Wednesday, 21st February 5pm. You have only one attempt at the assessment. If your attempt at the quiz is still in progress at the end of the allowed time, the answers you have filled in so far will be automatically submitted. You should read the information about assessed coursework before attempting this assessment.
WEEK 4 LECTURES AND TUTORIAL
- Lecture 1: Centrality measures, Degree and Eigenvector centrality. See chapter 3 Sec. 3.1-3.3 (part of 3.6). Katz and PageRank centralities See chapter 3 Sec. 3.4-3.5 (part of 3.6) & 3.9
- Lecture 2: Closeness and betweenness centralities. See chapter 3 Sec. 3.6-3.7
- Tutorial: Covering Formative Assignment 3.
HANDWRITTEN NOTES (will be avaible after the live sessions)
- Participate in the lectures and tutorial
-
WEEK4 Lecture 1 File
3.1MB
-
WEEK 4 Lecture 2 File
2.2MB
-
WEEK 4 Tutorial File
1.6MB
-
Formative Assignment 3 File
117.0KB
-
Solutions to Formative Assignment 3 File
142.5KB
-
-
ASSESSED COURSEWORK 2 (QUIZ)
-
-
Week 5 : Random graphs
-
WEEK 5 ACTIVITIES
- Participate in the lectures and tutorial
- Read Sections 4.1-4.5 & 4.8 Chapter 4 in the typeset Lecture notes.
- Attempt the questions from the Formative Assignment 4. These will be discussed in the tutorial.
- Complete and submit the assessed coursework 2 on the material of week 3-4 byWednesday, 21st February 5pm. This is a summative assessment (in the form of a QMPLUS quiz) that counts 4% towards your module mark. You have only one attempt at the assessment. If your attempt at the quiz is still in progress at the end of the allowed time, the answers you have filled in so far will be automatically submitted. You should read the information about assessed coursework before attempting this assessment.
WEEK 5 LECTURES AND TUTORIAL
- Lecture 1: Random graphs ensembles and distribution of the total number of links. See chapter 4 Sec. 4.1-4.3. Degree distribution of the random graphs ensembles. See chapter 4 Sec. 4.3 & 4.8
- Lecture 2: Poisson networks. See chapter 4 Sec. 4.4 & Sec. 4.8
- Tutorial: Covering Formative Assignment 4 + Feedback on Assessed Coursework Quiz 2
HANDWRITTEN NOTES (will be avaible after the live sessions)
- Participate in the lectures and tutorial
-
WEEK 5 Lecture 1 File
4.0MB
-
WEEK 5 Lecture 2 File
1.6MB
-
WEEK 5 Tutorial File
2.2MB
-
Formative Assignment 4 File
103.8KB
-
Solutions to Formative Assignment 4 File
120.5KB
-
-
Week 6 : Random graphs
-
WEEK 6 ACTIVITIES
- Participate in the lectures and tutorial.
- Read Sections 4.5-4.6 Chapter 4 in the typeset Lecture notes.
- Attempt the questions from the Formative Assignment 5. These will be discussed in the tutorial.
- Start working on the Assessed Coursework-Quiz 3 on the material of week 5-6. This is a summative assessment (in the form of a QMPLUS quiz) that counts 4% towards your module mark. The quiz opens on Friday, 1st March 6pm and closes on Wednesday, 6th March 5pm.
- You have only one attempt at the assessment. If your attempt at the quiz is still in progress at the end of the allowed time, the answers you have filled in so far will be automatically submitted. You should read the information about assessed coursework before attempting this assessment.
WEEK 6 LECTURES AND TUTORIAL
- Lecture 1: Emergence of the giant component in random graphs. See chapter 4 Sec. 4.6
- Lecture 2: Expected number of cliques in random graphs. See chapter 4 Sec. 4.7
- Tutorial: Covering Formative Assignment 5.
HANDWRITTEN NOTES (will be avaible after the live sessions)
- Participate in the lectures and tutorial.
-
WEEKS 6 Lecture 1 File
3.5MB
-
WEEK 6 Lecture 2 File
1.7MB
-
WEEK 6 Tutorial File
2.1MB
-
Formative Assignment 5 File
86.3KB
-
Solutions to Formative Assignment 5 File
119.8KB
-
ASSESSED COURSEWORK 3 (QUIZ)
-
-
Week 7
-
WEEK 7 ACTIVITIES
- Review the material covered in weeks 1-6
- Complete and submit the Assessed Coursework-Quiz 3 on the material of week 5-6 by Wednesday, 6th March 5pm. This is a summative assessment (in the form of a QMPLUS quiz) that counts 4% towards your module mark. You have only one attempt at the assessment. If your attempt at the quiz is still in progress at the end of the allowed time, the answers you have filled in so far will be automatically submitted. You should read the information about assessed coursework before attempting this assessment.
WEEK 7 LECTURES (No Lectures, no tutorial)
-
-
Week 8 : Scale-free networks
-
WEEK 8 ACTIVITIES
- Participate in the lectures and tutorial.
- Read Sections 5.1-5.5.3 Chapter 5 in the typeset Lecture notes.
- Attempt the questions from the Formative Assignment 6. These will be discussed in the tutorial.
- Start working on Assessed Coursework-4 on the material of week 5-6-8. This is a summative assessment that counts 4% towards your module mark. The coursework opens on Friday, 15th March 6pm and closes on Wednesday, 20th March 5pm. You should read the information about assessed coursework before attempting this assessment.
WEEK 8 LECTURES AND TUTORIALS
- Lecture 1: Scale-free networks.See chapter 5 Paragraphs 5.1-1.2.Scale-free networks. See chapter 5 Paragraph 5.2-5.5.4
- Lecture 2: Barabasi-Albert model (mean-field solution). See chapter 5 Paragraph 5.5.1-5.5.3
- Tutorial: Covering Formative Assignment 6
HANDWRITTEN NOTES (will be avaible after thelive lessons)
- Participate in the lectures and tutorial.
-
WEEK 8 Lecture 1 File
4.4MB
-
WEEK 8 Lecture 2 File
1.7MB
-
WEEK 8 Tutorial File
2.1MB
-
Formative Assignment 6 File
96.6KB
-
Solutions to Formative Assignment 6 File
137.1KB
-
Coursework 4 (Submit Coursework 4) Assignment
Please dowload below Assessed Coursework 4 and upload here your solution any time between
Friday, 15th March 6pm and Wednesday, 20th March 5pm
You should submit your work as a PDF file which should be a scan of a handwritten document. Any late submission will not be accepted.
This assignment will contribute 4% of your final mark for the module.
-
ASSESSED COURSEWORK 4 File
76.6KB
-
-
Week 9 : BA model
-
WEEK 9 ACTIVITIES
- Participate in the lectures and tutorial.
- Read Sections 5.5-5.6 Chapter 5 in the typeset Lecture notes.
- Attempt the questions from theFormative Assignment 7. These will be discussed in the tutorial.
- Complete and submit theAssessed Coursework-4 on the material of week 5-6-8 by Wednesday, 20th March 5pm. This is a summative assessment that counts 4% towards your module mark. You should read the information about assessed coursework before attempting this assessment.
WEEK 9 LECTURES AND TUTORIALS
- Lecture 1: Scale-free networks (mean-field solution). See chapter 5 Paragraphs 5.5.2. Scale-free networks (master equation). See chapter 5 Paragraphs 5.5.3
- Lecture 2: Growing network model with uniform attachment. See chapter 5 Paragraph 5.6
- Tutorial: Feedback on Assessed Coursework-4
HANDWRITTEN NOTES (will be avaible after thelive lessons)
- Participate in the lectures and tutorial.
-
WEEK 9 Lecture 1 File
3.3MB
-
WEEK 9 Lecture 2 File
1.9MB
-
WEEK 9 Tutorial File
1.3MB
-
Formative Assignment 7 File
92.3KB
-
Solutions to Formative Assignment 7 File
117.1KB
-
Further readings: BA model File
335.9KB
-
-
Week 10 : Other models of growing graphs
-
WEEK 10 ACTIVITIES
- Participate in the lectures and tutorial.
- Read Sections 6.1-6.3 Chapter 6 and Sections 7.1-7.3 Chapter 7 in the typeset Lecture notes.
- Attempt the questions from the Formative Assignment 8. These will be discussed in the tutorial.
- Start working on the Assessed Coursework 5 on the material ofof week 9-10. This is a summative assessment that counts 4% towards your module mark. The coursework opens Friday, 29th March 6pm and closes on Wednesday, 3rd April 5pm (deadline extended to Friday, 5th April 5pm). You should read the information about assessed coursework before attempting this assessment.
WEEK 10 LECTURES AND TUTORIALS
- Lecture 1: Bianconi-Barabasi model. See chapter 6 Paragraphs 6.1-6-3
- Lecture 2: Clustering coefficient. See chapter 7 Paragraphs 7.1-7.3
- Tutorial: Covering Formative Assignments 7 and 8
HANDWRITTEN NOTES (will be avaible after thelive lessons)
- Participate in the lectures and tutorial.
-
WEEK 10 Lecture 1 File
3.0MB
-
WEEK 10 Lecture 2 File
2.0MB
Click here to watch the recorded lecture: WEEK 10 Lecture 2
-
Formative Assignment 8 File
108.0KB
-
Solutions to Formative Assignment 8 File
145.8KB
-
Further readings: BB model File
197.3KB
-
Coursework 5 (submit Coursework 5) Assignment
Please dowload below Assessed Coursework 5 and upload here your solution any time between
Friday, 29th March 6pm and Wednesday, 3rd April 5pm (deadline extended to Friday, 5th April 5pm)
You should submit your work as a PDF file which should be a scan of a handwritten document. Any late submission will not be accepted.
This assignment will contribute 4% of your final mark for the module.
-
ASSESSED COURSEWORK 5 File
90.4KB
-
-
Week 11: Small-world networks
-
WEEK 11 ACTIVITIES
- Participate in the lectures and tutorial.
- Read Sections 7.1-7.6 Chapter 7 of the typeset Lecture notes.
- Attempt the questions from the Formative Assignment 9. These will be discussed in the tutorial.
- Complete and submit theAssessed Coursework 5 of week 9-10 byWednesday, 3rd April 5pm (deadline extended to Friday, 5th April 5pm). This is a summative assessment that counts 4% towards your module mark. You should read the information about assessed coursework before attempting this assessment.
WEEK 11 LECTURES AND TUTORIALS
- Lecture 1: Small-world properties. Cayley tree. See chapter 7 Paragraphs 7.4
- Lecture 2 Small-world properties.Random graphs. See chapter 7 Paragraph 7.6
- Tutorial: Covering Formative Assignment 9
HANDWRITTEN NOTES (will be avaible after thelive lessons)
- Participate in the lectures and tutorial.
-
WEEK 11 Lecture 1 File
4.0MB
-
Week 11 lecture 2 File
1.5MB
-
Week 11 tutorial File
1.6MB
-
Formative Assignment 9 File
99.8KB
-
Solutions to Formative Assignment 9 File
117.7KB
-
Further readings: WS small-world network model File
273.3KB
-
-
Syllabus
-
1. Networks (simple,directed weighted) and their representation with adjacency matrices and edgelists.
2. Basic definitions and metrics: network size and total numebr of links, degree, degree distribution, paths, subgraphs (loops and cliques), connected components.
3. Social networks and centrality measures: degree and eigenvector centrality, Katz and PageRank centrality, closeness, betweenness.
4. Erdős-Renyi random graph models: degree distribution, emergence of the giant connected component, expected number of cliques.
5. Scale-free networks. Random graphs with a given degree sequence. The Molloy and Reed criterion.
6. Citation networks and the linear preferential attachment. The Barabasi-Albert model and other models of growing graphs.
7. Small-world networks. Six degrees of separation. The clustering coefficient. Watts and Strogatz model.
8. The configuration model. The friendship paradox. The natural cutoff and the natural degree-degree correlations.
-
-
Module aims and learning outcomes
-
ACADEMIC CONTENT
This module covers:
- Structural properties of networks and Network Analysis.
- Random graph models.
- Scale-free networks and small-world networks.
- The configuration model.
DISCIPLINARY SKILLS
At the end of this module, students should be ableto:
- Characterize the structural properties of networks: degrees, degree distributions, paths, subgraphs, connected components.
- Use different centrality measures to quantify the role that different nodes have on complex networks.
- Use random graphs as null model for real networks, and be able to interpret the difference between real complex networks and random graphs.
- Calculate the first and second moment of the degree distributions.
- Predict the degree distribution of growing network models including model with uniform and preferential attachment.
- Acquire the mathematical knowledge to be able to understand the small-world distance properties and the friendship paradox in social networks.
ATTRIBUTES
At the end of this module, students should havedeveloped with respect to the following attributes:
- Acquire substantial bodies of new knowledge.
- Acquire and apply mathematical knowledge in a rigorous way to real-wold problems.
- Connect information and ideas within their field of study.
- Explain and argue clearly and concisely.
-
-
Assessment
-
The module will be assessed by
- assessed coursework, worth 20% of the overall mark;
- a final exam, worth 80% of the overall mark.
-
-
Teaching team
-
Add information here.
-
-
Hints and tips
-
Lectures
There will be three hours of lectures per week. Lectures will take place live and will be recorded. Lectures will use a virtual whiteboard and will follow the typed notes. Do your best to attend all lectures rather than watching recordings, to ensure you keep up with the module and have the opportunity to ask questions. During lectures you may want to take notes or annotate a copy of the typed notes.
Tutorials
There will be one hour of tutorials per week (starting from week 2), which may be listed as "seminars" in your timetable. Tutorials will take place live and will be recorded. In a typical tutorial we will recap key points from the week's lectures and we will solve some of the week's formative assignments, whose solution you don't need to turnin, but which you should be ready to discuss in the tutorial. Therewill also be an opportunity to discuss general course-related queries.
Assessment
There will be five assessed courseworks, each counting for 4% of your module mark. These will appear at two-week intervals, and you will have a few days to complete and submit each one (usually they open on a Friday and close at 5 pm on the following Wednesday). The final exam in May will count for 80% of your module mark.
-
-
Where to get help
-
Add information here.
-
-
General course materials
-
LECTURE NOTES File
6.9MB
The full lecture notes for the module written by Prof. Ginestra Bianconi when she was teaching the module (in 2020/21 and the in the previous years) are given here.These notes are intended to be a definitive record of what is examinable.
Information about what is taught in each week can be seen in the sections for the individual weeks below.
-
-
Coursework
-
ASSIGNMENT STRUCTURE AND SUBMISSION
There will be 5 assessed courseworks,with deadline in weeks 3, 5, 7, 9, 11. The 5 courseworks will respectively cover materials up to week 2, 4, 6, 8, 10
The first 3 assessed courseworks are quizzes, thelast 2 assessed courseworks are hand-written assignements.
Each of the 5 assessed coursework counts 4% towards yourmodule mark.
Usually the quizzes open on Fridays at 6pm and close at 5 pm on the following Wednesdays.
There is no time limit (however, the quiz should take less than an hour to complete). You have only one attempt at the quiz. During a quiz, If your attempt is still in progress at thedeadline, the answers you have filled in so far should now be automaticallysubmitted (whether or not you are actively working on thequiz-coursework). However, for your own reassurance, you are recommendedto explicitly submit your attempt wherever possible. Note that if youstart an attempt, or even just look at the questions, but are unable to finishdue to Extenuating Circ*mstances (ECs) such as illness you must emailmaths@qmul.ac.uk (with cc to the lecturer) before the deadline; if youdo not do this, your half-finished attempt will be automatically counted andany subsequent EC claim is likely to be rejected.
ACADEMIC INTEGRITY
You are encouraged to discuss the course materialand lecture notes withother students. However, your quiz-coursework submission must be yourown work. In particular, this means the following.
- You should do the quiz-coursework questions by yourself, from your own computer, and not share answers. It's OK to say to a friend "I think I need to understand the inclusion-exclusion principle, can you explain it to me?" but it's not OK to say "What is the answer to Question 2?".
FEEDBACK / MARKING
Feedback on courseworks 1-3 (quizzes)
As soon as the quiz-coursework deadline has closed,you will be able to see whether your answers to the quiz were right and whatyour marks are. Answers to a selection of quiz-courseworks will be discussed in the tutorials.
Feedback on couseworks 4-5
You will receive written feedback on your courseworks 4-5 after about one week from your submission.
To find a particular coursework, please go to the Module Content and scroll down to the appropriate week.
-
-
Exam papers
-
The final exam is a handwritten assessment that will be held online. The assessment will be available for a period of 3.5 hours, within which you must submit your solutions. You may log out and in again during that time, but the countdown timer will not stop. If your attempt is still in progress at the end of your 3.5 hours, any file you have uploaded will be automatically submitted.
The assessment has been designed so that to be completed within 3 hours. In completing this assessment:
• You may use books and notes.
• You may use calculators and computers, but you must show your working for any calculations you do.
• You may use the Internet as a resource, but not to ask for the solution to an exam question or to copy any solution you find.
• You must not seek or obtain help from anyone else.For training and preparation, consider the Formative Assignments of the module and the following past papers. A sample paper with solutions is available in the Exam Preparation and Past Papers topic.
-
Past papers for this module URL
-
Examples of solutions of past exam papers Folder
-
-
Week 12 + REVISION
-
WEEK 12 ACTIVITIES
- Participate in the lectures.
- Participate to the REVISION SESSION that will be in Lecture 2
- Read Sections 7.4 and 7.7 of Chapter 7 and 8.1,8.2, 8.4,8.5 Chapter 8 of the typeset Lecture notes.
- Attempt the questions from the Formative Assignment 10.
WEEK 12 LECTURES AND TUTORIALS
- Lecture 1: Uncorrelated networks. See chapter 8
- Lecture 2: Revision Session
HANDWRITTEN NOTES (will be avaible after thelive lessons)
-
Week 12 lecture 1 File
2.8MB
-
Week 12 tutorial File
1.3MB
-
Revision Lecture File
4.9MB
-
Final Exam 2023 File
164.1KB
-
Formative Assignment 10 File
88.9KB
-
Solutions to Formative Assignment 10 File
103.3KB
-
-
Exam Preparation and Past Papers
-
Sample Paper File
164.1KB
This exam paper is of the same style and standard as this year's exam
-
Example Solutions to the Sample Paper File
166.3KB
These are example solutions to the sample exam paper
-
Other past papers for this module URL
This is a link to many other past papers. Whilst these will examine roughly the same roughly the same content, the structure may be very different
-
-
Generated by Assessment Information block
Not available
-
Q-Review
-
Q-Review Recordings External tool
-
-
-
Early feedback questionnaire
Not available
-
Online Reading List
-
Assessment information
-
Assessment Pattern - 20% coursework + 80% final assessment
Format and dates for the in-term assessments - 5 online courseworks during term
Format of final assessment - handwritten assessment that will be held online.
Link to past papers - see above
Description of Feedback -Answers to a selection of quiz-courseworks will be discussed in the tutorials. Written feedback on your courseworks 4-5
-
-
Hidden section
Not available
-
Generated by Assessment Information block
Not available