CSC303 Spring 2024

Course Contents

Dates	Description of Lecture
Week 12, Apr 1-5	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, Mar 25-29	Congestion games and network traffic. Braess paradox. Clean lecture slides: slides. Live lecture slides: slides. No tutorial this week -- the Univerity is closed on March 29th.
Week 10, Mar 18-22	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, Mar 11-15	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, Mar 4-8	Choosing an initial set of adopters. Common knowledge vs local knowledge. Competitive influence spread. Contact networks and the spread of infection. Clean lecture slides: slides. Live lecture slides: slides. Tutorial: Midterm will take place during tutorial time, in the usual tutorial rooms. No Monday Whiteboard Wednesday Whiteboard
Week 7, Feb 26-Mar 1	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. Clean lecture slides: slides. Live lecture slides: slides. No tutorial slides as we are taking up A1. Monday Whiteboard Wednesday Whiteboard
Week 6, Feb 12-16	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. Clean lecture slides: slides. Live lecture slides: slides. Live Tutorial slides: slides. Monday Whiteboard Wednesday Whiteboard
Week 5, Feb 5-9	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. Clean lecture slides: slides. Live lecture slides: slides. Tutorial: practice problemset Note that this week's tutorial recordings are not very helpful as 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 :) Monday Whiteboard Wednesday Whiteboard
Week 4, Jan 29-Feb 2	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 Monday Whiteboard Wednesday Whiteboard
Week 3, Jan 22-26	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 Monday Whiteboard Wednesday Whiteboard
Week 2, Jan 15-19	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 Monday Whiteboard Wednesday Whiteboard
Week 1, Jan 8-12	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. Live lecture slides: slides. Monday Whiteboard Wednesday Whiteboard Friday Whiteboard All recordings are posted to Quercus (see "OCCS Student App" tab, download links under the "Files" tab). The Fri Jan 12 lecture has no OCCS recording, but a Zoom recording is available here.

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: Lecture & tutorial recordings can be found on Quercus (see "OCCS Student App" tab, download links under the "Files" tab).

Tentative Course Schedule

Week	Dates	Lecture Topics	Tutorial Topic	Suggested Readings
W1	Jan 8-12	Networks, graph concepts	N/A	Ch 1,2
W2	Jan 15-19	Strong and weak ties	Mini Lecture	Ch 3
W3	Jan 22-26	Homophily and Influence	Mini Lecture	Ch 4
W4	Jan 29-Feb 2	Structural balance	Paper Discussion	Ch 5
W5	Feb 5-9	Small worlds	Problem Set	Ch 20
W6	Feb 12-16	Power laws, Web link analysis	Mini Lecture	Ch 18,14
	Reading week
W7	Feb 26-Mar 1	Rumour spread, influence maximization	A1 Solutions	Ch 19
W8	Mar 4-8	Influence models, disease spread	Midterm	Ch 19,21
W9	Mar 11-15	Mitochondrial Eve, Bargaining power	Problem Set	Ch 21,12
W10	Mar 18-22	Stable marriage, Network traffic	Paper Discussion	Ch 8
W11	Mar 25-29	Braess' paradox, kidney exchange.	Univ. Closed	Ch 8
W12	Apr 1-5	Additional topics and course review.	A2 Solutions

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.