List of theory topics

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.

Session 1: Why studying Network Science

Before class

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

During class

• 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

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: We live in a small world

Before class

• Watch this 9-minutes video about The Science of Six Degrees of Separation
• Watch this 5-minutes video of explanation of network centrality measures

During class

• 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

After class

• 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

Session 3: Friends will be friends

Before class

• Watch the 1-minutes video on the Friendship Paradox
• Watch the 4-minutes video on clustering coefficients

During class

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

After class

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

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 4: PageRank and case study

Before class

• Watch this 5-minutes animation explaining PageRank

During class

• Lecture TT07: PageRank pdf
  • Exercise: compute simplified PageRank (spreadsheet)
• Lecture TT08: Case study on centrality 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

Session 5: Mid-term exam (October 23rd, 2024, 16:30)

Before class

Study on your own, try to solve exams from past years.

During class

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.

Session 6: Modelling homogeneous networks

Before class

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

During class

• 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

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

After class

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

Session 8: Modelling heterogeneous networks

Before class

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

During class

• 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

After class

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

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

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 embedding

Before class

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

During class

• 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

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

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.