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.
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.
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
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?"
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.
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.
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.
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
Welcome to the class
Who would benefit from taking it?
What do you need to succeed in it?
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?"
(exceptional scheduling)
The small-world experiment
Milgram's experiment
S.Milgram,
“The small world problem,”
Psychology today, 1967.
Slides:
Python Tutorial
A combinatorial small world
Markov Inequality, (Concentration Results)
A complex small world
Clustering Coefficient,
Rewiring & shortcuts
M. Granovetter,
“The strength of weak ties: A network theory revisited,”
Sociological theory, vol. 1, pp. 201–233, 1983.
Slides:
An algorithmic small world
Failure of uniform shortcuts
Harmonic distribution
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:
Catch-up
Proof of small-world Navigation
Handouts1:
Complete proof of the small world navigation
(dimension k=1)
due date: Thursday, September 20th (immediately before class)
A.2 Stand out: "Why do super nodes emerge in large networks? How does Google find and rank them?"
It's a (mostly) unfair world
Power law and Heavy Tail,
Light Tail, Long Tail, Lognormal
Background reading:
M. O. Lorenz,
“Methods of measuring the concentration of wealth,”
American Statistical Association, vol. 9, no. 70, pp. 209–219, 1905.
Why is this world unfair?
Proportional effect, Preferrential attachment
Power law as optimal choice
Artefacts
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.
How to spot important nodes?
betweenness, k-core).
Iterative algorithms
Background readings:
D. Segal, “The Dirty Little Secrets of Search,” The New York Times, 13-Feb.-2011.
Analysis of Iterative Algorithms
Eigenvalues, Spectral Gap
HITS and Page Rank
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?"
Finding Communities in Graphs?
Clustering Heuristics (betweenness,
modularity, conductance)
Spectral Partitioning
Finding Communities in Network?
Network of Enemies
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.
It will be about the two first themes of the class
"Connect" and "Stand-out"
A.4 Age: "How social networks evolve with time? Why do I feel evermore closer to everyone in Facebook?"
The surprising macroscopic evolution of networks?
Hierarchical Models
Evolution under the microscope, and its predictability
due date: Wednesday, November 7th (immediately before class)
Part B - Dynamics over Social Networks
B.1 Infect: "What characterizes epidemics on a network? Why are computer viruses so hard to eradicate?"
Epidemics: Continuous Evolution
Analysis of autonomous diff. equation
Evolution SI, SIS, SIR
Epidemics: Discrete Evolution
consequences of spectral property
Epidemics: Algorithms
Epidemics review & Catch-Up
a General gossip design result based
on conductance
due date: Tuesday, November 20th (immediately before class)
B.2 Adopt: "Can we predict how our neighbors influence us? How can my start-up product becomes viral?"
Influence: Everything is infectious
Threshold model on complete graph
Fixed point method
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.
Influence: Effect of graph topology
Cluster density,
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.
Epidemics: Discrete Evolution
critical mass vs. diminishing return
Maximizing spread of influence
Influence review & Catch-Up
Greedy Algorithms and their properties
due date: Tuesday, December 11th (at 4pm)
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?"
Sample
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?"
Review of recent works
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.