Online Social Networks and Media
Slides and References




Slides & References

Reading Material



Lecture 1: Introduction

Introduction to main problems about networks. Basic mathematic concepts


ˇ         Networks, Crowds, and Markets (chapters 1,2)

ˇ         The structure and function of complex networks (by M. E. Newman)


Lecture slides


Lecture 2: Network Measurements

Degree distributions. Measuring power-laws. Clustering Coefficient, Bow-tie structure, Homophily.

Strong and Weak ties.


ˇ         Networks, Crowds, and Markets (chapter 3)


Lecture slides (Part 1, Part 2)


Lecture 3: Strong and Weak ties

Strong and Weak ties. Bridges. Measurements in real networks


ˇ         Networks, Crowds, and Markets (chapter 3)


Lecture slides


Lecture 4: Network Models

Erdos-Renyi graphs. Configuration Model. Preferential Attachment. Small-world models. Forrest-Fire model.


ˇ         M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003

ˇ         M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics.

ˇ         B. Bollobas, Mathematical Results in Scale-Free random Graphs.

ˇ         D.J. Watts. Networks, Dynamics and Small-World Phenomenon, American Journal of Sociology, Vol. 105, Number 2, 493-527, 1999

ˇ         Watts, D. J. and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature 393:440-42, 1998

ˇ         Michael T. Gastner and M. E. J. Newman, Optimal design of spatial distribution networks, Phys. Rev. E 74, 016117 (2006).


Lecture slides


Lecture 5: Strong and Weak Ties, Betweeness, Affiliation networks

Strong and weak ties, Betweeness computation and clustering. Affiliation networks.


ˇ         Networks, Crowds, and Markets (Chapters 3 and 4)

ˇ         Mining Massive Datasets version 1.1 (Chapter 10)


Lecture slides (Part 1, Part 2)


Lecture 6: Navigation in a small world

Algorithm for searching in a small world network


ˇ         Networks, Crowds, and Markets (chapter 20)


Lecture slides


Lecture 7: Positive and Negative ties

Positive and Negative ties, Structural Balance


ˇ         Networks, Crowds, and Markets (chapter 5)


Lecture slides


Lecture 8: Information Cascades, Epidemics, Influence Maximization.

Game theoretic information cascade. Models for epidemic spread. Selecting influencers to maximize spread.


ˇ         Networks, Crowds, and Markets (chapters 19, 21)

ˇ         D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003.


Lecture slides (Part A, Part B, Part C)


Lecture 9: Link Analysis. Label propagation via Absorbing Random Walks.

HITS algorithm, PageRank algorithm. Absorbing Random Walks, Label propagation


ˇ         Networks, Crowds, and Markets (chapter 14)

ˇ         P. G. Doyle, J. L. Snell. Random Walks and Electrical Networks.

ˇ         D. Bindel, J. Kleinberg, S. Oren. How Bad is Forming Your Own Opinion? Proc. 52nd IEEE Symposium on Foundations of Computer Science, 2011.

Lecture slides (Part A, Part B)


Lecture 10: Link Prediction

Predicting future or missing links


ˇ         David Liben-Nowell, Jon Kleinberg. The Link Prediction Problem for Social Networks. J. American Society for Information Science and Technology.

ˇ         Aaron Clauset,Cristopher Moore, M. E. J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature 2008

Lecture slides


Lecture 11: Privacy in Social Networks

Privacy attacks. Releasing anonymized social networks


ˇ         L. Backstrom, C. Dwork, J. Kleinberg. Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography. Proc. 16th Intl. World Wide Web Conference, 2007.

ˇ         Kun Liu, Evimaria Terzi: Towards identity anonymization on graphs, ACM International Conference on Management of Data (SIGMOD) 2008.

ˇ         Michael Hay, Gerome Miklau, David Jensen, Donald F. Towsley, Philipp Weis: Resisting structural re-identification in anonymized social networks. PVLDB 1(1): 102-114 (2008), also in VLDB J. 19(6): 797-823 (2010)

ˇ         Bin Zhou, Jian Pei: Preserving Privacy in Social Networks Against Neighborhood Attacks. ICDE 2008: 506-515

ˇ         Lei Zou, Lei Chen, M. Tamer Özsu: K-Automorphism: A General Framework For Privacy Preserving Network Publication. PVLDB 2(1): 946-957 (2009)

ˇ         Elena Zheleva, Lise Getoor: To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles. WWW 2009: 531-540

ˇ         Arvind Narayanan, Vitaly Shmatikov: De-anonymizing Social Networks. IEEE Symposium on Security and Privacy 2009: 173-187

Lecture slides