Social and Information Networks, Spring 2021

Course Contents

This webpage will be populated with brief descriptions of actual material covered in lectures in reverse chronological order. It will also contain lecture slides and links to recordings (accessible via UTORid). This webpage will be frequently updated. Initially, I am using lecture slides from the Spring 2020 version of the course. I will be updating the material and developing some new material for some additional topics. Please point out any typos to the instructor.

Date Description of Lecture
Week 12, April 5-9 Monday finished last week's material on Braess Paradox and Kidney exchange. Friday is a fun review exercise.
Monday Recording: MSStream Link
Wed Tut Sec #3 Recording: [Link removed after Final Exam]
Friday Recording: MSStream Link
Week 12 Jeopardy & Bingo & Additional Topics. Note that the numbers in the slides in brackets are links, so you can click them to jump to the corresponding question. Tutorial this week will be covering the practice question solutions.
Week 11, March 29 - April 2 Finish covering week 10 material on properties of FPDA and MPDA. Congestion games and network traffic. Braess paradox, kidney exchanges, recap of course.
Monday Recording: MSStream Link
Wed Tut Sec #3 Recording: [Link removed after Final Exam]
Friday Recording: N/A, Statutory holiday
Final Week 11 slides. Tutorial this week will be covering the A2 solutions.
Week 10, March 22-26 Finish covering week 9 material on bargaining. The stable marriange (matching) problem. Gale Shapley algorithm(s): FPDA and MPDA. Properties of FPDA and MPDA algorithms. Other considerations regarding stable matching.
Monday Recording: MSStream Link
Wed Tut Sec #3 Recording: MSStream Link
Friday Recording: MSStream Link
Final Week 10 slides. Final Tutorial slides
Week 9, March 15-19 Finish covering the Week 8 material on common vs. local knowledge, and competitive influence spread. Finish chapter 21 with the discussion of genetic inheritance and ``Mitochondrial Eve''. Bargaining in a Network Exchange Model.
Monday Recording: MSStream Link
Wed Tut Sec #3 Recording: MSStream Link
Friday Recording: MSStream Link
Final Week 9 slides. Final Tutorial slides
Week 8, March 8-12 Choosing an initial set of adopters. Common knowledge vs local knowledge. Competitive influence spread. Contact networks and the spread of infection.
Monday Recording: MSStream Link
Wed Tut Sec #3 Recording: MSStream Link
Friday Recording: MSStream Link
Final Week 8 slides. Final Tutorial slides
Week 7, March 1-5 Finish looking at the role of link structure in Web ranking. Influence spread in a social network. A threshold model for influence spread. Determining the thresholds from the relative rewards. Complete cascades vs tightly knit blocking communities. Choosing an initial set of initial adopters.
Monday Recording: MSStream Link
Wed Tut Sec #1 Recording: [Link removed after Final Exam]
Wed Tut Sec #3 Recording: [Link removed after Final Exam]
Friday Recording: MSStream Link
Final Week 7 slides. Tutorial will not have the usual participation quiz, it will only be a review of A1 solutions.
Week 6, February 22-26 We consider the observed power laws for a number of social and information networks. Power law distributions bs a normal distributions. Power law distribution for the number of in-links to a Web page. To provide some plausible explanation of this phenomena, we consider the Kumar et al preferential attachment model for network dynamics. The sensitivity to randomness in the initial stages of a random dynamic process. The Saganik et al music downloading experiment. We then switch to chapter 14 and the role of link structure in Web search and ranking.
Monday Recording: MSStream Link
Wed Tut Sec #1 Recording: MSStream Link
Wed Tut Sec #3 Recording: MSStream Link
Friday Recording: MSStream Link
Final Week 6 slides. Final Tutorial slides
Week 5, February 8-12 Finished looking at the signed Laplacian matrix to find balanced subgraphs. The small worlds (6 degrees of separation) phenomena. The Watts-Strogatz model. Kleinberg's analysis lead to rank based distribution of friends. Real world geographical data supporting the power law that probability of a friend at rank r is ~1/r. The Liben-Nowell and Backstrom et al studies. Social distance. Adamic and Adar study.
Monday Recording: MSStream Link
Wed Tut Sec #1 Recording: MSStream Link
Wed Tut Sec #3 Recording: MSStream Link
Friday Recording: MSStream Link
Final Week 5 slides. Final Tutorial slides
Week 4, February 1-5 Chapter 5 and social networks with positive and negative signs. Balanced triangles and strongly balanced networks. The strong balance theorem. Weak structural balance. Using the Signed Laplacian matrix to find balanced subgraphs.
Monday Recording: MSStream Link
Wed Tut Sec #1 Recording: MSStream Link
Wed Tut Sec #3 Recording: MSStream Link
Friday Recording: MSStream Link
Final Week 4 slides. Final Tutorial slides
Week 3, January 25-29 The Rosenshtein et al follup of Sintos and Tsaparas. The role of approximation algorithms. More on communities. Homophily. The Schelling segregation model. The selection vs influence question. Social-affiliation networks. Three types of closures. Calculating the probability of new link creation.
Monday Recording: MSStream Link
Wed Tut Sec #1 Recording: MSStream Link
Wed Tut Sec #2 Recording: MSStream Link
Wed Tut Sec #3 Recording: MSStream Link
Friday Recording: MSStream Link
Final Week 3 slides. Final Tutorial slides and Anderson Slides.
Week 2, January 18-22 What can be learned from network structure. Strong and weak ties. Clustering coefficient. Triadic closure. Weak ties, overlap, communities. The Sintos and Tsaparas study.
Slides covered on Monday: Monday 18th slides.
Monday Recording: MSStream Link
Wed Tut Sec #2 Recording: MSStream Link
Wed Tut Sec #3 Recording: MSStream Link
Friday Recording: MSStream Link
Final Week 2 slides. Final Sec 3 Tutorial slides. Sec 2 Tutorial slides.
Week 1, January 11-15 Course administration. Motivation for the course: networks everywhere and of growing importance. Examples of networks and discussion of basic graph theory concepts and facts using examples.
Slides covered on Monday: Monday 11th slides.
Monday Recording: MSStream Link
Slides covered on Wed.: Wed 13th slides.
Wed Recording: MSStream Link
Friday Recording: MSStream Link
Full Week 1 Slides: Week 1 slides.

Tentative Course Schedule.

Week No. Dates Tentative Schedule of Topics Suggested Readings
0 Jan 11-15 Intro Course Contents
1 Jan 11-15 Networks, graph concepts EK Ch 1 and 2
2 Jan 18-22 Strong and weak ties EK Ch 3
3 Jan 25-29 Homophily and Influence EK Ch 4
4 Feb 1-5 Structural balance EK Ch 5
5 Feb 8-12 Small worlds EK Ch 20
5+ Feb 15-19 Reading week
6 Feb 22-26 Power laws, Web link analysis EK Ch 18,14
7 March 1-5 Rumour spread, influence maximization EK Ch 19
8 March 8-12 Influence models, disease spread EK Ch 19,21
9 March 15-19 Mitochondrial Eve, Bargaining power EK Ch 21,12
10 March 22-26 Stable marriage, Network traffic EK Ch 8
11 March 29- April 2 Braess' paradox, kidney exchange. EK Ch 8
12 April 5-9 Additional topics and course review.
Exam Period April 13-23

Additional course materials will be placed here.

  • Probability Primer
  • Link to Michael Kearns' course
  • Starbird et al paper on strategic information spread
  • The Backstrom and Kleinberg article on Facebook romantic relations
  • The Bearman and Moody article on the relevance of the clustering coefficient
  • The Oracle of Bacon
  • The Sintos and Tsaparas article on labeling weak and strong ties
  • The Rozenshtein et al. article on labeling weak and strong ties
  • McDermott et al. article on the role of influence on divorce
  • Hulchanski Septermber 2018 article in Toronto Star newspaper
  • Hulchanski February 2019 talk at Ryerson University
  • Ordozgoiti et al. paper on finding balanced subgraphs
  • The Backstrom, Sun, Marlow geographical location article.
  • Adamic and Adar social distance article.
  • Kumar et al paper on web links and the power law distribution.
  • Salganik et al article studying the impact of influence in determining popularity.
  • Barabasi and Albert preferential attachnment article.
  • Vosoughi et al. article on the spread of news on Twitter
  • Price's study of the citation network.
  • The Braubach and Kearns article on interesting individuals.
  • Bonato et al preferential attachment model.
  • Avin et al article on elites in a social network
  • Avin et al article on preferential attachment as a unque equilibrium
  • Kempe et al article on choosing an initial set of influential adopters.
  • Mitochondrial Eve demo.