On this page, you find all the materials (slides, handouts, assignments) organized chronologically.
Most importantly, the columns "Important notions/methods" summarize for each lectures the particular definition and method that you need to digest, and will be used in assignments and exams.

Preliminary


Date & Title
Important notions/methods
Readings and Materials
Tuesday, September 4th

Welcome to the class
What is this class about?
Who would benefit from taking it?
What do you need to succeed in it?
Background reading:
J. Giles,
“Computational social science: Making the links.,”
Nature, vol. 488, no. 7412, pp. 448–450, 23-Aug.-2012.

Slides:

Part A - Structural Properties of Social Networks


A.1 Connect: "What makes social network connected? Why are we all within 6 clicks in Facebook?"


Date & Title
Important notions/methods
Readings and Materials
Wednesday, September 5th
(exceptional scheduling)

The small-world experiment
Geometric expansion and its fallacies
Milgram's experiment
Sociological must-read #1:
S.Milgram,
“The small world problem,”
Psychology today, 1967.

Slides:

Thursday, September 6th
Python Tutorial

Slides:

Tuesday, September 11th

A combinatorial small world
Random Graph, Threshold function,
Markov Inequality, (Concentration Results)
Slides:

Thursday, September 13th

A complex small world
Weak ties, Local Bridge,
Clustering Coefficient,
Rewiring & shortcuts
Sociological must-read #2:
M. Granovetter,
“The strength of weak ties: A network theory revisited,”
Sociological theory, vol. 1, pp. 201–233, 1983.

Slides:

Tuesday, September 18th

An algorithmic small world
Greedy routing,
Failure of uniform shortcuts
Harmonic distribution
Sociological must-read #3:

M. McPherson, L. Smith-Lovin, and J. M. Cook,
“Birds of a Feather: Homophily in Social Networks,”
Annual review of sociology, vol. 27, pp. 415–444, Jan. 2001.

Slides:

Thursday, September 20th

Catch-up
Analysis of small world Navigation
Proof of small-world Navigation
Slides:


Handouts1:
Complete proof of the small world navigation
(dimension k=1)
Additional documents:


A.2 Stand out: "Why do super nodes emerge in large networks? How does Google find and rank them?"


Date & Title
Important notions/methods
Readings and Materials
Tuesday, September 25th

It's a (mostly) unfair world
Pareto's principle
Power law and Heavy Tail,
Light Tail, Long Tail, Lognormal
Slides:


Background reading:
M. O. Lorenz,
“Methods of measuring the concentration of wealth,”
American Statistical Association, vol. 9, no. 70, pp. 209–219, 1905.
Thursday, September 27th

Why is this world unfair?
Reinforcement, Yule's evolution
Proportional effect, Preferrential attachment
Power law as optimal choice
Artefacts
Slides:


Handouts #2:
Complete proof (including when N(0) is not 0) of
the power law obtained by Yule process.


Sociological must-read #4:H. Simon, “On a Class of Skew Distribution Functions”,
Biometrika, vol. 42, no. 3, pp. 425–440, Dec. 1955.
Tuesday, October 2nd
How to spot important nodes?
Measuring centrality (degree, closeness,
betweenness, k-core).
Iterative algorithms
Slides:

Background readings:
D. Segal, “The Dirty Little Secrets of Search,” The New York Times, 13-Feb.-2011.

Thursday, October 4th
Analysis of Iterative Algorithms
Adjacency Matrix,
Eigenvalues, Spectral Gap
HITS and Page Rank
Slides:
Additional documents:
  • Assignment 2 -- "Explaining and Extracting Important Nodes"
    due date: Tuesday, October 23rd (immediately before class)

A.3 Divide: "How to identify natural communities and dissension? Who is likely to love or hate my blog?"


Date & Title
Important notions/methods
Readings and Materials
Tuesday, October 9th
Finding Communities in Graphs?
Review of Homework #1

Clustering Heuristics (betweenness,
modularity, conductance)
Spectral Partitioning
Slides:



Thursday, October 11th
Finding Communities in Network?
Network of Enemies
Impact of size of communityCommunity formation,Structural Balance

Slides:

Sociological must-read #5:R. I. M. Dunbar,
“Coevolution of Neocortical Size, Group-Size
and Language in Humans,”
Behav Brain Science, vol. 16, no. 4, pp. 681–694, 1993.

Sociological must-read #6:
D. Cartwright and F. Harary,“Structural balance: a generalization of Heider's theory.,”Psychological Review, vol. 63, no. 5, pp. 277–293, 1956.



Midterm
Come prepared for a 1h15 quizz
It will be about the two first themes of the class
"Connect" and "Stand-out"
  • Assignment for this part is combined with the next part.

A.4 Age: "How social networks evolve with time? Why do I feel evermore closer to everyone in Facebook?"


Date & Title
Important notions/methods
Readings and Materials
Tuesday, October 23rd

The surprising macroscopic evolution of networks?
Densification, Shrinking Diameter,
Hierarchical Models
Slides:

Thursday, October 25th

Evolution under the microscope, and its predictability
Triangle closure, Link prediction
Slides:


Part B - Dynamics over Social Networks


B.1 Infect: "What characterizes epidemics on a network? Why are computer viruses so hard to eradicate?"


Date & Title
Important notions/methods
Readings and Materials
Thursday, November 1st

Epidemics: Continuous Evolution
Logistic dynamics,
Analysis of autonomous diff. equation
Evolution SI, SIS, SIR
Slides:

Wednesday, November 7th

Epidemics: Discrete Evolution
Graph adjacency matrix,
consequences of spectral property
Slides:

Thursday, November 8th
Epidemics: Algorithms

Slides:

Tuesday November 13th

Epidemics review & Catch-Up
Gossip algorithm, their strength
a General gossip design result based
on conductance
Slides:


B.2 Adopt: "Can we predict how our neighbors influence us? How can my start-up product becomes viral?"

Date & Title
Important notions/methods
Readings and Materials
Thursday, November 15th

Influence: Everything is infectious
Conformity, influence,
Threshold model on complete graph
Fixed point method
Slides:

Sociological must-read #7:B. Ryan and N. C. Gross,“The diffusion of hybrid seed corn in two Iowa communities,”Rural sociology, vol. 8, no. 1, pp. 15–24, 1943.
+ S. Asch,“Opinions and social pressure,”Scientific American, 1955.

Tuesday November 20th

Influence: Effect of graph topology
Adoption process in general graph
Cluster density,
Slides:

Sociological must-read #8:M. Granovetter,“Threshold Models of Collective Behavior,”The American Journal of Sociology, vol. 83, no. 6, pp. 1420–1443, May 1978.

Tuesday, November 27th

Epidemics: Discrete Evolution
Influence function,
critical mass vs. diminishing return
Maximizing spread of influence
Slides:


Thursday, November 29th

Influence review & Catch-Up
Submodular function
Greedy Algorithms and their properties
Slides:



B.3 Sample & Secure: "How to measure social networks? Why I have less Facebook friends than them?"

"How can I make sure that a Facebook friend is not a bot?"


Date & Title
Important notions/methods
Readings and Materials
Tuesday, December 4th

Sample

Slides:


  • No home-assignment for this part of the class.

B.4 Learn & Trade : "How to make (good) collective decisions? Should I trust the reviews in Yelp?"

"Can social networks be useful to the economy? Is Facebook share really worth $38 or $5?"


Date & Title
Important notions/methods
Readings and Materials
Thursday, December 6th

Review of recent works

Slides:

Sociological must-read #9:F. Galton,“Vox Populi,” Nature, vol. 75, no. 1949, pp. 450–451, Mar. 1907.Sociological must-read #10:R. S. Burt, Structural Holes: The Social Structure of Competition. Harvard University Press, 1992.


  • No home-assignment for this part of the class.