CSC303

Social and Infoirmation Networks Spring 2020

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. Initially, I am using lecture slides from the Spring 2019 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.

. . . . . . . . . : .

Tentative Course Schedule.

Date Description of Lecture
Week 12, March 30,April 3 Braess paradox, kidney exchanges, recap of course. See Week 12 slides.
Week 11, March 23,27 The stable marriange (matching) problem. Gale Shapley algorithm(s): FPDA and MPDA. Properties of FPDA and MPDA algorithms. Other considerations regarding stable matching. Congestion games and network traffic. See Week 11 slides.
Week 10, March 16,20 Finish chapter 21 with the discussion of genetic inheritance and ``Mitochondrial Eve''. Bargaining in a Network Exchange Model. See Week 10 slides.
Week 9, March 9,13 Choosing an inital set of adopters. Common knowledege vs local knowledge. Competitve infliuence spread. Contact networks and the spread of infection. See Week 9 slides.
Week 8, March 2 Influence spread in a social newtork. 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. See Week 8 slides.
Week 7, February 25,27 Given the size of massive information networks (the web) and social networks, extracting information about these networks requires sublinear time algorithms. Fortunately, information networks and social networks usually enjoy special properties that will fasciliate fast algorithms. Who are the ``elites'' in a social network. This will lead us next week to a discussion of influence spread in a social network. See Week 7 slides.
Week 6, February 10,12 We consider the observed power laws for a number of social and informatkion 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 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 3,7 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 27-31 Finish discussion of Chapter 4. Calculating the probability of new link creation. The Schelling segregation model. Chapter 5 and social networks with positive and negative signs. Balanced triangles and strongly balanced networks. The strong balance theorem. Weak structural balance. See Week 4 slides.
Week 3, January 20-24 The Rosenshtein et al follup of Sintos and Tsaparas. The role of approximation algorithms. More on communities. Homophily. The selection vs influence question. Social-affiliation networks. Three tyopes of closures. See Week 3 slides.
Week 2, January 13-17 What can be learned from network structure. Strong and weak ties. Clustering coefficent. Triadic closure. Weak ties, overlap, communities. The Sintos and Tsaparas study. See Week 2 slides.
Week 1, January 6-10 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 Tentative Schedule of Topics Suggested Readings
0 Jan 6-10 Intro Course Contents
1 Jan 6-10 Networks, graph concepts EK Ch 1 and 2
2 Jan 13-17 Strong and weak ties EK CH 3
3 Jan 20-24 Homophily and Influence EK ch 4
4 Jan 27-31 Structural balance EK Ch 5
5 Feb 3-7 Small worlds EK Ch 20
6 Feb 10-14 Power laws, Web link analysis EK CH 18,14
6+ Feb 17-21 Reading week
7 Feb 24-28 Large networks and computation. Begin influence maximization.
8 March 2-6 Rumour spread, influence maximization EK 19
9 March 9-13 Influence models, disease spread EK Ch 19,21
10 March 16-20 Mitochondrial Eve, Bargaining power Ch 21,12
11 March 23-27 Stable marriage, Network traffic Ch 8
12 March 30-April 3 Braess' paradox, kidney exchange, review of course Ch 8
Exam Period April 6-30

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 /a>
  • 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 artcle on the role of influence on divorce
  • Hulchanski Septermber 2018 article in Toronto Star newspaper
  • Hulchanski February 2019 talk at Ryerson University
  • 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.
  • 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.