🚧 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 Nearpod or Google Spreadsheets. Please avoid distractions: place your phone in airplane mode, close all other windows in your computer, and try to stay focused. We will pause frequently during the session to help you regain focus. 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.
- Take a look at the list of theory topics, practice sessions, and evaluation rules
- Lecture TT02: examples of complex networks odp/pdf
- Nearpod: find examples of networks
- Lecture TT03: applications networks science odp/pdf
- Course overview
- Overview of theory topics
- Overview of practice sessions
- Overview of evaluation rules
- Lecture TT04: graph theory basics odp/pdf
- Google Spreadsheet: draw degree distribution
- Lecture TT05: sparsity and connectivity odp/pdf -- MOVED TO SESSION 02
- Nearpod: left-project and right-project a graph
- Read chapter 0 of "A first course on network science"
- Read chapter 2 of the book by Barabási
- 📺 Watch the 45-minutes documentary The Emergence of Network Science -- if you can't watch this before the next lecture, watch it at some other point during the trimester
- 📺 Watch the one-hour talk "The Sociological Science Behind Social Networks and Social Influence" by Nicholas Christakis (has subtitles in English).
- See presentation TT01: a personal introduction odp/pdf
- 📺 Watch the 4-minutes video on clustering coefficient
- 📺 Watch the 17-minutes video on the ER random graph model by Lada Adamic (has subtitles in English)
- Lecture TT06: clustering coefficient odp/pdf
- Nearpod: compute local clustering coefficients
- Lecture TT07: the random network (ER) model odp/pdf
- Nearpod: compute expected number of links and expected average degree
- Lecture TT08: properties of random networks odp/pdf -- MOVED TO SESSION 03
- Nearpod: find actors with large degree
- Nearpod: 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 TT09: scale-free networks odp/pdf
- Nearpod: compute nodes with an expected degree
- Lecture TT10: distances in scale-free networks odp/pdf -- MOVED TO SESSION 04
- Nearpod: calculate friendship paradox
- Read the chapter 4 of the book by Barabási
- 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 the 13-minutes video on preferential attachment from a course on fractals and scaling
- Lecture TT11: preferential attachment odp/pdf
- Nearpod: compute nodes with an expected degree
- Lecture TT12: degree under preferential attachment odp/pdf -- MOVED TO SESSION 05
- Nearpod: copy model
- Read the chapter 5 of the book by Barabási
- 📺 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
- 📺 Watch this 5-minutes animation explaining PageRank
- Lecture TT14: hubs and authorities odp/pdf
- Google spreadsheet: compute hub and authority scores iteratively
- Lecture TT15: pagerank odp/pdf -- MOVED TO SESSION 06
- Google spreadsheet: compute simplified PageRank
- 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
- 📺 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.
- Lecture TT17: closeness odp/pdf
- Google spreadsheet: compute closeness and harmonic closeness
- Lecture TT18: betweenness odp/pdf
- Nearpod: run the Brandes and Newman algorithm for betweenness
- 📺 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
Study on your own TT02-TT12, TT14, try to solve exams from past years. Ask your questions in the forum.
We will have a mid-term exam covering topics: TT02-TT12, TT14.
- 📺 Watch the 10-minutes lecture on why detecting communities by Lada Adamic
- Lecture TT19: community structure odp/pdf
- Lecture TT20: network flows odp/pdf
- Nearpod: write min-cut and max-flow equations
- Nearpod: run randomized s-t cut algorithm
- Read the sections 9.1 and 9.2 of the book by Barabási
- Read the sections 7.1 and 7.2 of Algorithm Design by Kleinberg and Tardos (it includes a greedy algorithm: Ford-Fulkerson, that we will not study formally)
- Study the Ford-Fulkerson algorithm in the sections 7.1 and 7.2 of the book by Kleinberg and Tardos and make sure you can follow this step-by-step run of the algorithm
- If you still did not get the min-cut, max-flow duality:
- 📺 Watch this 2-minutes video on The min-cut, max-flow duality
- 📺 Watch this 10-minutes Numerical example
- 📺 Watch this 10-minutes video on k-core decomposition
- 📺 Watch this 5-minutes presentation on Charikar's algorithm
- Lecture TT21: k-cores odp/pdf
- Nearpod: perform a k-core decomposition
- Lecture TT22: dense sub-graphs odp/pdf
- Nearpod: run Charikar's algorithm
- Read sections 1 and 2 of this paper on the k-core decomposition -- do not worry if you cannot follow all details
- Read Charikar's paper on his algorithm -- do not worry if you cannot follow all details
- 📺 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
- See presentation TT23: spectral graph clustering odp/pdf
- 📺 Watch the lessons on graph Laplacian, spectral graph partitioning, and partitioning in three or more communities 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 TT24: spreading phenomena odp/pdf
- Lecture TT25: models of influence odp/pdf
- Google spreadsheet: simulate linear threshold model
- Google spreadsheet: simulate independent cascade model
- Read chapter 19 of the book by Easley and Kleinberg
- 📺 Watch this 13-minutes infection simulations
- Lecture TT26: epidemics odp/pdf
- Nearpod: compute number of infected over time
- Lecture TT27: epidemics on graphs odp/pdf
- Read chapter 10 of the book by Barabási
- Read chapter 21 of the work by Easley and Kleinberg
- 📺 Watch this 24-minutes explanation of the mathematics of the SIR model for COVID
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.
Theory topics TT01-TT06 and TT13 closely follow "Networks Science" book (2016) and course by Albert-László Barabási. In other 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.