home


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
September 8th
Welcome to the class
Motivation for learning concepts of social network.
What's in the class? Should you take it?



Part I - Structure


Part A.1 - It's a small world, but what kind?


Date & Title
Important notions/methods
Materials
September 8th
A Combinatorial Small World
The Small World experiment,
Random Graph, Threshold functions,
Probabilistic Method, Markov Inequality

September 15th
A Complex Small World
Concentration Inequality,
Monotone properties, Expander
Strong Weak ties, Clustering Coefficient,
Uniformly Augmented Lattice,
Greedy routing, and its failure

September 22nd
An Algorithmic Small World
Homophily, Biased Augmented Lattice, Small World Navigation,

September 29th
Catchup
Proof of Small World Navigation



Materials:

Main References:
  1. Milgram, S. (1967). The small world problem. Psychology Today.
  2. Granovetter, M. (1983). The strength of weak ties: A network theory revisited. Sociological Theory, 1, 201–233.
  3. McPherson, M., Smith-Lovin, L., & Cook, J. M. (2001). Birds of a Feather: Homophily in Social Networks. Annual Review of Sociology, 27, 415–444.

Part A.2 - Why is there super nodes and how to find those?


Date & Title
Important notions/methods
Materials
October 6th
Power law and their causes
Light tail, Heavy Tail, Lorenz Curve
Effect of Heavy tails, Long tail effect,
Power law distribution,
Generative models by reinforcement

October 13th
The ranking problem
Degree/Closeness/Betweenness Centrality, k-core decomposition
Iterative methods: Hubs and Authorities Algorithms

October 20th
Catchup
Proof of convergence and limits of iterative algorithms


Materials:

Main References:
  1. Lorenz, M. O. (1905). Methods of measuring the concentration of wealth. Publications of the American Statistical Association, 9(70), 209–219.
  2. Simon, H. (1955). On a Class of Skew Distribution Functions. Biometrika, 42(3/4), 425–440.
  3. Yule, G. U. (1925). A Mathematical Theory of Evolution, Based on the Conclusions of Dr. J. C. Willis, F.R.S. Philosophical Transactions of the Royal Society of London. Series BContaining Papers of a Biological Character, 213, 21–87.
  4. Mitzenmacher, M. (2004). A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2), 226–251.

Part A.3 - Which groups are relevant to understand networks?


Date & Title
Important notions/methods
Materials
October 27th
Communities and Balance
Divisive and Agglomerative Community Detection,
Modularity, Louvain method, Structural Balance


Main References:
  1. Dunbar, R. I. M. (1993). Coevolution of Neocortical Size, Group-Size and Language in Humans. Behavioral and Brain Sciences, 16(4), 681–694.
  2. Cartwright, D., & Harary, F. (1956). Structural balance: a generalization of Heider's theory. Psychological Review, 63(5), 277–293. doi:10.1037/h0046049


Part B - Dynamics


Part B.1 - Can we predict the spread of epidemics?


Date & Title
Important notions/methods
Materials
Skipped, materials included for correctness
Epidemics
Logistic dynamics, SI, SIS, SIR
Spectral Analysis of epidemic process
Gossip algorithm


Main References:
  1. Massoulié, L., & Draief, M. (2009). Epidemics and Rumors in Complex Networks (pp. 1–125). Cambridge University Press.
  2. Shah, D. (2009). Gossip Algorithms. Foundations and Trends® in Networking, 3(1).
  3. Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., et al. (1987). Epidemic algorithms for replicated database maintenance. PODC '87: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing.

Part B.2 - Can we leverage properties of influence?


Date & Title
Important notions/methods
Materials
November 10th
Adoption, Contagion
Influence, Peer Pressure, Conformity,
Threshold model, Contagion Threshold, Cluster Density


Main References:
  1. Granovetter, M. (1978). Threshold Models of Collective Behavior. The American Journal of Sociology, 83(6), 1420–1443.
  2. Morris, S. (2000). Contagion. The Review of Economic Studies, 67(1), 57–78.
  3. Kleinberg, J. M. (2007). Cascading behavior in networks: Algorithmic and economic issues. Algorithmic Game Theory.

Part B.3 - When does collective decision reach an optimal choice?


Date & Title
Important notions/methods
Materials
November 17th
Wisdom of the Crowd
iterative consensus, Naive Learning
Balance, Minimal Dispersion, Unif. Prominent Family


Materials:

Main References:
  1. Degroot, M. H. (1974). Reaching a Consensus. Journal of the American Statistical Association, 69(345), 118–121. doi:10.1080/01621459.1974.10480137
  2. Galton, F. (1907). Vox Populi. Nature, 75(1949), 450–451. doi:10.1038/075450a0
  3. Golub, B., & Jackson, M. O. (2010). Naive learning in social networks and the wisdom of crowds. American Economic Journal: Microeconomics, 2(1), 112–149. doi:10.1257/mic.2.1.112


Part C - Discover


Part C.1 - What is the best way to crawl a graph?


Date & Title
Important notions/methods
Materials
November 24th
Random walk for Unbias Crawl and Authentication
Friendship paradox, Crawl, Random Walk
Unbiased estimator, Mixing time, Sybil attack
File Not Found
File Not Found


Main References:
  1. Feld, S. (1991). Why Your Friends Have More Friends than You Do? American Journal of Sociology.
  2. Kurant, M., Gjoka, M., Butts, C., & Markopoulou, A. (2011). Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks. Proceedings of ACM SIGMETRICS.
  3. Levin, D., Peres, Y., & Wilmer, E. (2009). Markov chains and mixing times. Books.Google.com.

Part C.2 - Can we find a posteriori the source of a diffusion?


Part C.3 - Can we recognize users across multiple graphs?


Main References:
  1. Korula, N., & Lattanzi, S. (2014). An efficient reconciliation algorithm for social networks. Proceedings of VLDB, 7(5), 377–388.
  2. Pedarsani, P., & Grossglauser, M. (2011). On the privacy of anonymized networks. Presented at the KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining,  ACM Request Permissions. doi:10.1145/2020408.2020596
  3. Yartseva, L., & Grossglauser, M. (2013). On the performance of percolation graph matching. Presented at the COSN '13: Proceedings of the first ACM conference on Online social networks,  ACM Request Permissions. doi:10.1145/2512938.2512952


Part D - Bird's eye view of 2014 Social Network Research


In parallel to the fundamental results seen in class, we will survey recent papers, primarily taken from the last instalment of the ACM Conference on Online Social Network Conference.

Date & Title
Important notions/methods
Materials
October 6th
Centrality, Micro-reviews, Anonymity




References:
  1. Cohen, E., Delling, D., Pajor, T., & Werneck, R. F. (2014). Computing classic closeness centrality, at scale (pp. 37–50). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660465
  2. Vasconcelos, M., Almeida, J., Gonçalves, M., Souza, D., & Gomes, G. (2014). Popularity dynamics of foursquare micro-reviews (pp. 119–130). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660484
  3. Peddinti, S. T., Ross, K. W., & Cappos, J. (2014). “On the internet, nobody knows you're a dog” (pp. 83–94). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660467

Date & Title
Important notions/methods
Materials
October 13th
Democracy and Partisanship, OSN ads



References
  1. Etter, V., Herzen, J., Grossglauser, M., & Thiran, P. (2014). Mining democracy (pp. 1–12). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660476
  2. An, J., Quercia, D., & Crowcroft, J. (2014). Partisan sharing (pp. 13–24). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660469
  3. Liu, Y., Kliman-Silver, C., Bell, R., Krishnamurthy, B., & Mislove, A. (2014). Measurement and analysis of osn ad auctions. COSN '14: Proceedings of the 2nd ACM Conference on Online Social Networks, 139–150. doi:10.1145/2660460.2660475

Date & Title
Important notions/methods
Materials
October 20th
Privacy to third service



References
  1. Ramachandran, A., Kim, Y., & Chaintreau, A. (2014). “I knew they clicked when i saw them with their friends” (pp. 239–246). Presented at the COSN '14: Proceedings of the 2nd ACM conference on Online social networks, New York, New York, USA: ACM Press. doi:10.1145/2660460.2660461