List of theory topics

These materials should not be considered final until the end of the course. Materials from previous editions can be found in other branches of the repository for the course.

There are 11 theory sessions of 2 hours each. They will all take place face-to-face. Please bring your laptop.

Before each class, there are short videos you should watch. They are up to 20 minutes in total, and watching them requires some preparation/scheduling on your part. Please set aside time in your schedule to watch these videos before coming to class, ideally on the day before.

During class, I will present the contents using slides and we will do together some exercises using Padlets or Google Spreadsheets. Please avoid distractions: place your phone in airplane mode, close all other windows in your computer, and try to stay focused. In one of the sessions, a midterm exam will be taken, and at the end of the course, a final exam will be taken. The exam questions are based exclusively on the materials shown or discussed in the lectures during class.

After each session, there is some reading for you to do. These readings will be much easier after you have attended each lecture, will bring depth to what you learn in class, and will help you remember these contents better. Think of these readings as a form of continuous studying that will save you time and effort when preparing for the exams.

Session 1: Introduction

Before class

• Take a look at the list of theory topics, practice sessions, and evaluation rules

During class

• Lecture TT01: Complex Networks odp/pdf
  • First minute of The hidden networks of everything
  • Exercise: find examples of networks (pin board)
• Lecture TT02: applications networks science odp/pdf
• Course overview
  • Overview of theory topics
  • Overview of practice sessions
  • Overview of evaluation rules
• Lecture TT03: graph theory basics odp/pdf
  • Exercise: draw degree distribution (spreadsheet)
  • Exercise: left-project and right-project a graph

(Note: in 2023, we arrived until the end of degree distribution of TT03, the rest goes to the next session.)

After class

• Read chapter 2 of the book by Barabási
• Read chapter 0 of “A first course on network science”

Optional/additional material

Both of these are great to provide context for the course, and will help you stay motivated. I strongly suggest you set aside some time to watch them within the first 2-3 weeks of the trimester.

• Watch the 45-minutes documentary The Emergence of Network Science
• Watch the one-hour talk “The Sociological Science Behind Social Networks and Social Influence” by Nicholas Christakis (has subtitles in English).

Session 2: Distances, homophily, triangles

Before class

• Watch the 4-minutes video on clustering coefficient

During class

• Lecture TT04: connectivity odp/pdf
  • Quick exercise: find strongly connected components
• Lecture TT05: homophily and triangles odp/pdf
  • Exercise: homophilic, heterophilic, or neutral (pin board)
  • Exercise: compute local clustering coefficients (pin board)
• Lecture TT06: closeness odp/pdf
  • Exercise: compute closeness and harmonic closeness (spreadsheet)

After class

• Watch this 6-minutes video on Why we prefer people just like us, and why that’s potentially dangerous by Nicholas Christakis

Session 3: Betweenness, hubs, and authorities

Before class

• Watch this 5-minutes explanation of network centrality measures
• Watch the first 15-minutes of this 26-minutes video on degree, betweenness, and closeness as centrality measures by Lada Adamic. The first half of the video is about degree, the second half about betweenness and closeness.
• Watch the 12-minutes explanation of Hubs and Authorities by Daniel Romero
  • Or watch the 15-minutes explanation of Hubs and Authorities by Jure Leskovec

During class

• Lecture TT07: betweenness odp/pdf
  • Exercise: compute node betweenness (pin board)
  • Exercise: run the Brandes and Newman algorithm for betweenness
• Lecture TT08: hubs and authorities odp/pdf – In 2023 we moved the computation to the next session
  • Exercise: compute hub and authority scores iteratively (spreadsheet)

After class

• Watch the rest of the 26-minutes video on degree, betweenness, and closeness as centrality measures by Lada Adamic. The first half of the video is about degree, the second half about betweenness and closeness.
• Read sections 10.2.3 on betweenness and 10.2.4 on the Girvan-Newman algorithm in Mining Massive Datasets
• Read section 3.6 on betweenness and graph partitioning of chapter 3 of the book by Easley and Kleinberg

Session 4: PageRank and case study

Before class

• Watch this 5-minutes animation explaining PageRank

During class

• Lecture TT09: pagerank odp/pdf
  • Exercise: compute simplified PageRank (spreadsheet)
• Lecture TT10bis: case study on centrality odp/pdf - notebook

After class

• Read the chapter 14 of the book by Easley and Kleinberg
• Watch the (10-minutes each) lessons on PageRank 2.5, 2.6 by Jure Leskovec
• Watch the lessons matrix formulation of PageRank and PageRank and random walks by Jure Leskovec

Extra content: more on PageRank

• Lecture TT10: pagerank extra material odp/pdf

Session 5: Mid-term exam (October 20th, 2023)

Before class

Study on your own, try to solve exams from past years. Ask your questions in the forum.

During class

We will have a mid-term exam; there will be no lecture after the exam. The topics for the exam will be TT01-TT09, TT10bis.

Session 6: Random networks (ER model)

Before class

• Watch the 17-minutes video on the ER random graph model by Lada Adamic (has subtitles in English)

During class

• Lecture TT11: the random network (ER) model odp/pdf
  • Exercise: guess the formula for expected number of links, using NetLogo to run simulations (pin board)
  • Exercise: compute expected number of links and expected average degree
• Lecture TT12: properties of random networks odp/pdf
  • Exercise: guess critical point at which a giant connected component emerges, using NetLogo to run simulations (pin board)
  • Exercise: find actors with large distance from Kevin Bacon (pin board)
  • Exercise: find critical N for a graph to be connected

After class

• Read chapter 3 of the book by Barabási

Session 7: Scale-free Networks

Before class

• Watch this 20-minutes video on Zipf, Pareto, and power laws by Lada Adamic. It is a great explanation of a phenomenon that goes well beyond networks.

During class

• Lecture TT13: scale-free networks odp/pdf
  • Exercise: compute nodes with an expected degree
• Lecture TT14: distances in scale-free networks odp/pdf
  • Exercise: compare average distances estimators for some networks

After class

• Read the chapter 4 of the book by Barabási

Optional/additional material

• If you are not sure whether you understood the friendship paradox or not, or if you want to learn more about it, watch this half-hour explanation of the friendship paradox

Session 8: Preferential attachment

Before class

• Watch the 13-minutes video on preferential attachment from a course on fractals and scaling

During class

• Lecture TT16: preferential attachment odp/pdf
  • Exercise: guess slope of degree distribution, using NetLogo to run simulations (pin board)
  • Exercise: write formula for number of nodes and edges over time
• Lecture TT17: degree under preferential attachment odp/pdf
• Lecture TT15: the friendship paradox odp/pdf
  • Exercise: numerical example of friendship paradox (pin board)
  • Exercise: compute expected degree of neighbors

After class

• Read the chapter 5 of the book by Barabási

Optional/additional material

• Lecture TT18: other growth models odp/pdf
  • Exercise: copy model

Session 9: Communities

Before class

• Watch this 10-minutes video on k-core decomposition
• Watch the 10-minutes lecture on why detecting communities by Lada Adamic

During class

• Lecture TT19: k-cores odp/pdf
  • Exercise: perform a k-core decomposition
• Lecture TT20: community structure odp/pdf
• Lecture TT21: finding communities odp/pdf
  • Exercise: indicate if communities are strong or weak
  • Exercise: compute cut size under two different partitions (pin board)
  • Exercise: compute modularity

After class

• Read the sections 9.1 and 9.2 of the book by Barabási

Optional/additional material

• Read sections 1 and 2 of this paper on the k-core decomposition – do not worry if you cannot follow all details

Session 10: Spectral graph clustering

Before class

• Watch the lessons on graph Laplacian and spectral graph partitioning by Jure Leskovec

During class

• Lecture TT22: spectral graph embedding odp/pdf
  • Exercise: perform random 2D projection of a graph

After class

• Watch the lesson on partitioning in three or more communities by Jure Leskovec at Stanford

Optional/additional materials

• Watch the lessons on heuristics for finding communities, and community finding algorithms by Lada Adamic
• Watch the lessons on detecting communities as clusters and what makes a good clustering by Jure Leskovec at Stanford

Session 11: Spreading Phenomena

Before class

• Watch this 10 minutes crash course on social influence explaining some psychology concepts related to influence
• Watch this 7 minutes overview of network diffusion elements
• Watch this 13-minutes infection simulations

During class

• Lecture TT23: spreading phenomena odp/pdf
  • Exercise: explain three contagion variants, using NetLogo to run simulations (pin board)
  • Exercise: indicate phenomena that spread virally (pin board)
• Lecture TT24: models of influence odp/pdf
  • Exercise: simulate linear threshold model (spreadsheet)
  • Exercise: simulate independent cascade model (spreadsheet)
  • Exercise: list assumptions of these models (pin board)

After class

• Read chapter 10 of the book by Barabási
• Read chapter 19 of the book by Easley and Kleinberg
• Read chapter 21 of the work by Easley and Kleinberg
• Watch this 24-minutes explanation of the mathematics of the SIR model for COVID

Optional/additional material

• Lecture TT25: epidemics odp/pdf

Final Exam (December 11th, 2023)

The final exam will include the random network model (TT11-TT12), scale-free networks (TT13-TT14), the preferential attachment model (TT15-T17), community detection (TT19-TT21), spectral methods (TT22), and spreading phenomena (TT23-TT24). This excludes decks not seen in class, optional/additional slide decks, and slides marked “Extra”.

Notes

These slides are made with LibreOffice and the TexMaths extension, which allows to easily enter and edit LaTeX equations that are embedded as images in the slides.

Note that the source files include some solutions, while the PDF files do not include them. Use this while studying: do not look at the solutions until you have tried to solve the problem yourself.

Sources/credits

Some theory topics closely follow the “Networks Science” book (2016) and course by Albert-László Barabási. In all cases, the sources are indicated either at the beginning or in the footer of the slides. Please feel free to use, copy, and adapt contents from these slides for whatever purposes, giving proper attribution.

Slides available under a Creative Commons license unless specified otherwise.