CSC303

Course Contents

This webpage will be populated with brief descriptions of actual material covered in lectures in reverse chronological order. Ths webpage will be frequently updated. Please point out any typos to the instructor.

. . . . . . . . . .

Tentative Course Schedule.

Date	Description of Lecture
Week 12, April 2,4	Finish congestion networks and Braess' paradox. The Price of Anarchy. Kidney exchange networks. Recap of course. Student presentation of some critical reviews. See Week 12 slides.
Week 11, March 25,27	Stable marriage problem. Gale-Shapley Deferred Acceptance algorithm. Female and Male optimal stable matches. Start congestion networks. See Week 11 slides.
Week 10, March 18,20	Finish chapter 21 and the discussion of Mitochodrrial Eve. Chapter 12 and Exchange Networks and the Nash bargaining solution. Stable and balanced outcomes. We just started to discuss the stable marriage problem and I have included some slides dealing with the topic. See also slides for Week 11. See Week 10 slides.
Week 9, March 13,15	Choosing an initial set of adopters. Finish the discussion of chapter 19. We then begin Chapter 21 and the study of disease spread. See Week 9 slides.
Week 8, March 4,6	We finish the discussion of chapter 17 and direct benefirt effects. See Week 8 slides. We go on to discuss Chapter 19 and casades in the context of networks. We also consider the problem of finding an initial set of influential adopters so as to spread infliuence.
Week 7, February 25,27	This week considers cascades (Chapter 16) and direct benefit effects. Monday's lecture was on cascades (i.e., the slides ending at slide 22) and emphasizes the idea that such cascades can be rational, but that they can also be fragile and result in the wrong outcome. The main techincal idea is the use of Bayes rule. Wednesday we begin discussing chapter 17 and direct benefit effects. See Week 7 slides.
Week 6, February 11,13	We consider the observed power law 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 dynmaic 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. See Week 6 slides.
Week 5, February 4,6	The small worlds (6 degrees of separation) phenomena. The Watts-Strogatz model. Kleinberg's analysis lead to rank based distribution of friends. Real world geographaphic 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. See Week 5 slides.
Week 4, January 28,31	The Schelling segregation model. Social networks with positive and negative signs. Balanced triangles and strongly balanced networks. Strong strucral balance and the balance theorem. Weak structural balance. See Week 4 slides.
Week 3, January 21,23	Finish up Sintos and Tsaparas article. The role of approximation algorithms. Homophily. The selection vs influence question. Social-affiliation networks. See Week 3 slides.
Week 2, January 14,16	What can be learned from network structure. Strong and weak ties. Clustering coefficent. Triadic closure. Communities. See Week 2 slides.
Week 1, January 7,9	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. See Week 1 slides for introductory comments, motivation, and some examples of networks.

Week no	Dates	Topic	Suggested Readings
0	Jan 7,9	Intro	Course Contents
1	Jan 7,9	Networks, graph concepts	EK Ch 1 and 2
2	Jan 14,16	Strong and weak ties	EK CH 3
3	Jan 21,23	Homophily and Influence	EK ch 4
4	Jan 28,30	Structural balance	EK Ch 5
5	Feb 4,6	Small worlds	EK Ch 20
6	Feb11,13	Power laws, Web link analysis	EK CH 18,14
6+	Feb 18,20	Reading week
7	Feb 25,27	Cascades, direct benefit effects	EK Ch 16,17
8	March 4,6	Direct benefits, Cascades in a network, influence maximization	EK Ch 17,19
9	March 13,15	Influence maximization, additional influence models, disease spread	EK Ch 19,21
10	March 18,20	Mitochondrial Eve, Power and network exchange	Ch 21,12
11	March 25,27	Stable marriage, Network traffic	Ch 8
12	April 1,3	Finishing up, review, and some possible review presentations
Exam Period	April 6-30

Additional course materials will be placed here.

Probability Primer

Link to Michael Kearns course

The Backstrom and Kleinberg article on Facebook romantic relations

The Sintos and Tsaparas article on labeling weak and strong ties

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.

Kempe et al article on choosing an initial set of influential adopters.