There are 12 theory sessions of 2 hours each. They will all take place face-to-face. Please bring your laptop. One theory session is devoted to the mid-term exam (see below).
🚧 These materials should not be considered final until the end of the course. Theory sessions from 6 to 12 will be uploaded after the mid-term exam.
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, or on the blackboard.
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 continuous studying that will save time and effort when preparing for the exams.
Exams. After four sessions, a midterm exam will be taken. 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. You will be allowed to bring your notes to the exams. No laptops or phones will be allowed.
- Take a look at the list of theory topics, practice sessions, and evaluation rules
- Lecture TT01: Networks: Introduction pdf
- 📺 First minute of The hidden networks of everything
- Exercise: find examples of networks (pin board)
- Course overview
- Overview of theory topics
- Overview of practice sessions
- Overview of evaluation rules
- Lecture TT02: Graph Theory: Basics pdf
- Exercise: draw degree distribution (spreadsheet)
- Exercise: left-project and right-project a graph
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).
- 📺 Watch this 9-minutes video about The Science of Six Degrees of Separation
- 📺 Watch this 5-minutes video of explanation of network centrality measures
- Lecture TT03: Graph Theory: Connectivity pdf
- Quick exercise: find strongly connected components
- Lecture TT04: Graph Theory: Centrality pdf
- Exercise: compute closeness and harmonic closeness (spreadsheet)
- Exercise: compute node betweenness (pin board)
- Exercise: run the Brandes and Newman algorithm for betweenness
- 📺 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.
- 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
- 📺 Watch the 1-minutes video on the Friendship Paradox
- 📺 Watch the 4-minutes video on clustering coefficients
- Lecture TT05: Graph Theory: Degree Correlations pdf
- Exercise: average nearest neighbors' degree in uncorrelated networks (blackboard)
- Lecture TT06: Graph Theory: Clustering, and Homophily pdf
- Exercise: compute local clustering coefficients (pin board)
- Exercise: homophilic, heterophilic, or neutral (pin board)
- 📺 Watch this 6-minutes video on Why we prefer people just like us, and why that's potentially dangerous by Nicholas Christakis
- 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
- 📺 Watch this 5-minutes animation explaining PageRank
- Lecture TT07: PageRank pdf
- Exercise: compute simplified PageRank (spreadsheet)
- Lecture TT08: Case study on centrality pdf - notebook
- 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
Study on your own, try to solve exams from past years.
We will have a mid-term exam; there will be no lecture after the exam. The topics for the exam will be from lectures TT01-TT07.
- 📺 Watch the 17-minutes video on the ER random graph model by Lada Adamic (has subtitles in English)
- Lecture TT09: Network models: Erdos Renyi (ER) networks pdf
- Exercise: guess the formula for the expected number of links
- Exercise: compute the expected number of links and expected average degree
- Lecture TT10: Network models: properties of ER networks pdf
- Exercise: guess the critical point at which a giant connected component emerges
- Exercise: find critical N for a graph to be connected
- Read chapter 3 of the book by Barabási
- 📺 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.
- Lecture TT11: Scale-free (SF) networks pdf
- Exercise: compute nodes with an expected degree
- Lecture TT12: Distances in SF networks pdf
- Exercise: compare average distances estimators for some networks
- Read the chapter 4 of the book by Barabási
- 📺 Watch the 13-minutes video on preferential attachment from a course on fractals and scaling
- Lecture TT13: Network models: Barabasi-Albert networks pdf
- Exercise: write formula for number of nodes and edges over time
- Lecture TT14: Network models: Properties of BA networks pdf
- Read the chapter 5 of the book by Barabási
- 📺 Watch this 10-minutes video on k-core decomposition
- 📺 Watch the 10-minutes lecture on why detecting communities by Lada Adamic
- Lecture TT15: Community structure pdf
- Exercise: perform a k-core decomposition
- Exercise: indicate if communities are strong or weak
- Exercise: compute cut size under two different partitions (pin board)
- Lecture TT16: Community detection pdf
- Exercise: compute modularity
- Exercise: invent a variant of the ER model that generates graphs having two communities
- Read the sections 9.1 and 9.2 of the book by Barabási
- Read sections 1 and 2 of this paper on the k-core decomposition -- do not worry if you cannot follow all details
- 📺 Watch the lessons on graph Laplacian and spectral graph partitioning by Jure Leskovec
- Lecture TT17: spectral graph theory pdf
- Exercise: perform random 2D projection of a graph
- Lecture TT18: spectral graph embedding pdf
- Exercise: spectral projection of a graph
- 📺 Watch the lesson on partitioning in three or more communities by Jure Leskovec at Stanford
- 📺 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
- 📺 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
- Lecture TT19: Introduction to Network Dynamics pdf
- Exercise: indicate phenomena that spread virally (pin board)
- Lecture TT20: Information diffusion pdf
- Exercise: simulate linear threshold model (spreadsheet)
- Exercise: simulate independent cascade model (spreadsheet)
- Read chapter 19 of the book by Easley and Kleinberg
- 📺 Watch this 13-minutes infection simulations
- 📺 Watch this 24-minutes explanation of the mathematics of the SIR model for COVID
- Lecture TT21: Modelling Epidemics pdf
- Exercise: How to reduce R0 of an epidemic
- Lecture TT22: Epidemics on Networks pdf
- Read chapter 10 of the book by Barabási
- Read chapter 21 of the work by Easley and Kleinberg
The final exam will include the material seen in class after the midterm exam.
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.