Course Contents

Date Description of Lecture
Week 12, April 3-7 Monday we covered last week's material on Kidney exchange, and a quick recap. Wednesday is a fun review exercise.
Pictures of the brainstormed blackboards of course concepts, and themes are in Quercus, under Files.
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.
Week 11, March 27-31 Congestion games and network traffic. Braess paradox.
Clean lecture slides: slides.
Live lecture slides: slides.
Tutorial this week will be covering the solutions to assignment 2.
Monday Whiteboard
Wednesday Whiteboard
Week 10, March 20-24 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.
Clean lecture slides: slides.
Live lecture slides: slides.
Live Tutorial slides: slides.
Monday Whiteboard
Wednesday Whiteboard
Week 9, March 13-17 Finish chapter 21 with the discussion of genetic inheritance and ``Mitochondrial Eve''. Bargaining in a Network Exchange Model.
Tutorial: practice problemset 2
Clean lecture slides: slides.
Live lecture slides: slides.
Monday Whiteboard
Wednesday Whiteboard
Week 8, March 6-10 Choosing an initial set of adopters. Common knowledge vs local knowledge. Competitive influence spread. Contact networks and the spread of infection.
We didn't get to cover transient contacts or competitive spread, but we'll cover this material next week.
Clean lecture slides: slides.
Live lecture slides: slides.
Tutorial: Midterm will take place during tutorial time, in the usual tutorial rooms.
Monday Recording: MSStream Link
Wednesday Recording: MSStream Link
Friday Tutorial Recording: MSStream Link
Week 7, Feb 27 - Mar 3 Influence spread in a social network. The spread of fake news in Twitter. 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.
We reached up to the threshold induced by rewards; the remaining material will be finished in week 8.
Clean lecture slides: slides.
Live lecture slides: slides.
No tutorial slides as we are taking up A1.
Week 6, Feb 13-17 We consider the observed power laws for a number of social and information networks. Power law distributions vs. 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.
We didn't have time to finish justifying the convergence of PageRank, so that will be done next week.
Clean lecture slides: slides.
Live lecture slides: slides.
Live Tutorial slides: slides.
Week 5, Feb 6-10 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.
Tutorial: practice problemset
Clean lecture slides: slides.
Live lecture slides: slides.
All recordings posted to Quercus (see "OCCS Student App" tab, download links under the "Files" tab).
Note that this week's tutorial recordings are not very helpful it was group work without slides, but if you have questions about any of the practice problems, you can ask on Piazza or in office hours :)
Week 4, Jan 30 - Feb 3 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.
Clean lecture slides: slides.
Live lecture slides: slides.
Live tutorial slides: Tutorial slides
All recordings posted to Quercus (see "OCCS Student App" tab, download links under the "Files" tab)
Week 3, Jan 23-27 Homophily. The Schelling segregation model. The selection vs influence question. Social-affiliation networks. Three types of closures. Calculating the probability of new link creation.
Clean lecture slides: slides.
Live lecture slides: slides.
Live tutorial slides: Tutorial slides and Prof. Ashton's slides
All recordings posted to Quercus (see "OCCS Student App" tab, download links under the "Files" tab)
Week 2, Jan 16-20 What can be learned from network structure. Strong and weak ties. Clustering coefficient. Triadic closure. Weak ties, overlap, communities. The Sintos and Tsaparas study. The Rozenshtein et al follup of Sintos and Tsaparas. The role of approximation algorithms.

Clean lecture slides: slides.
Live lecture slides: slides.
Live tutorial slides: Tutorial slides
All recordings posted to Quercus (see "OCCS Student App" tab, download links under the "Files" tab)
Week 1, Jan 9-13 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.
Clean lecture slides: slides [Updated Jan 16 to clarify connected component vs. subgraph].
Live lecture slides: slides [Updated Jan 16 to clarify connected component vs. subgraph].
All recordings posted to Quercus (see "OCCS Student App" tab, download links under the "Files" tab)


Note 1: "clean" slides are for students who like to annotate -- they contain no transitions or anouncements. "live" slides are updated as I make changes, and they contain announcements, updates, slide transitions, and possibly minor clarifications, corrections or additional examples.


Note 2: Download links for lecture & tutorial recordings can be found on Quercus.

Tentative Course Schedule

Dates

Lecture Topics

Tutorial Topic

Suggested Readings

Jan 9-13

Networks, graph concepts

N/A

Ch 1,2

Jan 16-20

Strong and weak ties

Mini Lecture

Ch 3

Jan 23-27

Homophily and Influence

Mini Lecture

Ch 4

Jan 30-Feb 3

Structural balance

Paper Discussion

Ch 5

Feb 6-10

Small worlds

Problem Set

Ch 20

Feb 13-17

Power laws, Web link analysis

Mini Lecture

Ch 18,14

Feb 20-24

Reading week

Feb 27-Mar 3

Rumour spread, influence maximization

A1 Solutions

Ch 19

Mar 6-10

Influence models, disease spread

Midterm

Ch 19,21

Mar 13-17

Mitochondrial Eve, Bargaining power

Problem Set

Ch 21,12

Mar 20-24

Stable marriage, Network traffic

Paper Discussion

Ch 8

Mar 27-31

Braess' paradox, kidney exchange.

A2 Solutions

Ch 8

April 3-7

Additional topics and course review.

N/A

 

Linear Algebra Review

Although linear algebra is not a core focus of the course, you should be familiar with the concepts of matrix multiplication, block matrix multiplication, span, matrix null space, linear independence, orthonormal bases, eigenvalues and eigenvectors. For a quick review (~20 pages) of the above and more, you can read sections 1-3.9, and 3.12 of Kolter's Linear Algebra Review course, as well as section 7.3.2 on block matrices from Cherney, et al.'s Linear Algebra textbook
For a more detailed/technical review, you may want to consult Tyler Holden's MAT223 lecture notes (Sections 3.4, 4.4, 4.5, and 4.7), or Beezer's more rigorous A First Course in Linear Algebra

Probability Review

For a quick review of the relevant concepts (~4 pages), you can read up to B.15 (inclusive) of the Probability Primer

Learning through digital spaced repetition

As part of your weekly practice quiz, you will be asked to write 3 flashcards about what you think was the most important definition, proof, or concept from the last week's lecture.
Since I'm asking you write these flashcards, I strongly recommend that you put them into a free tool such as Anki that can automatically schedule and review them for you. For instructions, as well as why I think this is useful to you (both in CSC303, and beyond), please see the following document.

Additional Course Materials:

Additional resources, demos and papers will be posted here as the term progresses:

  • 2022 online offering of CSC303 (you should be able to access most recordings)
  • 2021 online offering of CSC303 (you should be able to access most recordings)
  • Probability Primer (only up to B.15, inclusive)
  • Link to Michael Kearns' course
  • yEd Graph Editor is a good, free, multiplatform graph editor (may be helpful for assignments)
  • A web based graph editor suggested by last year's students (may be helpful for assignments)
  • Starbird et al paper on strategic information spread
  • The Oracle of Bacon
  • The Backstrom and Kleinberg article on Facebook romantic relations
  • The Bearman and Moody article on the relevance of the clustering coefficient
  • 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
  • Reeves yellow paper on unconscious bias in the evaluation of writing
  • Paper on influence in obesity; note there's a video illustrating change over time as well
  • 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.
  • Interactive eigenvector demo
  • 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.
  • 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.