Topic outline

  • Announcements

    Collapse all Expand all

  • 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)

    • File icon
      WEEK 1 Lecture 1 File
      6.2 MB
    • File icon
      WEEK 1 Lecture 2 File
      2.7 MB

  • 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: Covering Formative Assignment 1.


        HANDWRITTEN NOTES  (will be avaible after the live sessions)

      • File icon
        WEEK 2 Lecture 1 File
        3.6 MB
      • File icon
        WEEK 2 Lecture 2 File
        1.7 MB
      • File icon
        WEEK 2 Tutorial File
        1.5 MB
      • File icon
        Formative Assignment 1 File
        93.3 KB
      • File icon
        Solutions to Formative Assignment 1 File
        95.9 KB
      • Quiz icon
        ASSESSED COURSEWORK 1 (QUIZ)

    • Week 3 : Basic measures

      • WEEK 3 ACTIVITIES

        • Participate in the lectures 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)

        • File icon
          WEEK 3 Lecture 1 File
          3.1 MB
        • File icon
          WEEK 3 Lecture 2 File
          2.8 MB
        • File icon
          WEEK 3 Tutorial File
          1.5 MB
        • File icon
          Formative Assignment 2 File
          771.6 KB
        • File icon
          Solutions to Formative Assignment 2 File
          787.9 KB

      • 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.
          • Attempt the 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)

        • File icon
          WEEK4 Lecture 1 File
          3.1 MB
        • File icon
          WEEK 4 Lecture 2 File
          2.2 MB
        • File icon
          WEEK 4 Tutorial File
          1.6 MB
        • File icon
          Formative Assignment 3 File
          117.0 KB
        • File icon
          Solutions to Formative Assignment 3 File
          142.5 KB
        • File icon
          Further readings: Article 1 File
          361.8 KB
        • Quiz icon
          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 by Wednesday, 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)

        • File icon
          WEEK 5 Lecture 1 File
          4.0 MB
        • File icon
          WEEK 5 Lecture 2 File
          1.6 MB
        • File icon
          WEEK 5 Tutorial File
          2.2 MB
        • File icon
          Formative Assignment 4 File
          103.8 KB
        • File icon
          Solutions to Formative Assignment 4 File
          120.5 KB

      • Week 6 : Random graphs

      • 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 the live lessons)


        • File icon
          WEEK 8 Lecture 1 File
          4.4 MB
        • File icon
          WEEK 8 Lecture 2 File
          1.7 MB
        • File icon
          WEEK 8 Tutorial File
          2.1 MB
        • File icon
          Formative Assignment 6 File
          96.6 KB
        • File icon
          Solutions to Formative Assignment 6 File
          137.1 KB
        • Assignment icon
          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.


        • File icon
          ASSESSED COURSEWORK 4 File
          76.6 KB

      • 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 the Formative Assignment 7. These will be discussed in the tutorial.
          • Complete and submit the Assessed 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 the live lessons)

        • File icon
          WEEK 9 Lecture 1 File
          3.3 MB
        • File icon
          WEEK 9 Lecture 2 File
          1.9 MB
        • File icon
          WEEK 9 Tutorial File
          1.3 MB
        • File icon
          Formative Assignment 7 File
          92.3 KB
        • File icon
          Solutions to Formative Assignment 7 File
          117.1 KB
        • File icon
          Further readings: BA model File
          335.9 KB

      • 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 of of 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 the live lessons)

        • File icon
          WEEK 10 Lecture 1 File
          3.0 MB
        • File icon
          WEEK 10 Lecture 2 File
          2.0 MB

          Click here to watch the recorded lecture: WEEK 10 Lecture 2

        • File icon
          Formative Assignment 8 File
          108.0 KB
        • File icon
          Solutions to Formative Assignment 8 File
          145.8 KB
        • File icon
          Further readings: BB model File
          197.3 KB
        • Assignment icon
          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.


        • File icon
          ASSESSED COURSEWORK 5 File
          90.4 KB

      • Week 11: Small-world networks

      • 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 able to:

          • 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 have developed 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 turn in, but which you should be ready to discuss in the tutorial. There will 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

        • File icon
          LECTURE NOTES File
          6.9 MB

          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, the last 2 assessed courseworks are hand-written assignements.

          Each of the 5 assessed coursework counts 4% towards your module 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 the deadline, the answers you have filled in so far should now be automatically submitted (whether or not you are actively working on the quiz-coursework).  However, for your own reassurance, you are recommended to explicitly submit your attempt wherever possible.  Note that if you start an attempt, or even just look at the questions, but are unable to finish due to Extenuating Circumstances (ECs) such as illness you must email maths@qmul.ac.uk (with cc to the lecturer) before the deadline; if you do not do this, your half-finished attempt will be automatically counted and any subsequent EC claim is likely to be rejected.

           

          ACADEMIC INTEGRITY

          You are encouraged to discuss the course material and lecture notes with other students.   However, your quiz-coursework submission must be your own 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 what your 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.



        • URL icon
          Past papers for this module URL
        • Folder icon
          Examples of solutions of past exam papers Folder

      • Week 12 + REVISION

      • Exam Preparation and Past Papers

      • Q-Review

      • 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