network

Online Social Networks and Media
Slides and References

 

Home

Homework


Slides & References

Reading Material

Resources

 

Lecture 1: Introduction

Introduction to main problems about networks. Basic mathematic concepts

Material:

ˇ         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.

Material:

ˇ         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

Material:

ˇ         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.

Material:

ˇ         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.

Material:

ˇ         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

Material:

ˇ         Networks, Crowds, and Markets (chapter 20)

 

Lecture slides

 

Lecture 7: Positive and Negative ties

Positive and Negative ties, Structural Balance

Material:

ˇ         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.

Material:

ˇ         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

Material:

ˇ         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

Material:

ˇ         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

Material:

ˇ         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