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) Social Media Mining (chapters 1,2) Lecture slides (pptx, pdf). Introduction to Graph Theory (pptx, pdf) (slides from Social Media Mining) Lecture 2: Network Measurements Degree distributions. Measuring power-laws. Clustering Coefficient, Effective Diameter, Bow-tie structure, Homophily. Material: M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics. Networks, Crowds, and Markets (Chapter 3) Lecture slides (pptx, pdf) Lecture 3: Network Models Erdos-Renyi graphs. Configuration Model. Preferential Attachment. Small-world models. Forrest-Fire model. Kronecker graphs 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). J. Leskovec, J. M. Kleinberg, C. Faloutsos. Graphs over time: Densification laws, shrinking diameters and possible explanations. TKDD 2007 J. Leskovec, D. Chakrabarti, J. M. Kleinberg, C. Faloutsos. Kronecker graphs: An approach to modeling networks. Journal of Maching Learning, 2010. Lecture slides (pptx, pdf) Lecture 4: Community Detection Communities in Social Networks, Clustering, Betweeness,Modularity Material: Networks, Crowds, and Markets (Chapter 3) Mining Massive Datasets (Chapter 10) Social Media Mining (Chapter 6) Tan, Steinbach, Kumar. Introduction to Data Mining (Chapter 8) S. Fortunato. Community Detection in Graphs. Lecture slides: (pptx, pdf) Lecture 5: Graph Partitioning, Densest Subgraph Graph Partitioning, Spectral Clustering. The Densest Subgraph problem. Material: Mining Massive Datasets (Chapter 10) Social Media Mining (Chapter 6) S. Fortunato. Community Detection in Graphs. Moses Charikar. Greedy Approximation Algorithms for Finding Dense Components in a Graph. Aris Gionis. Dense subgraph discovery (slides) David Kempe, Structure and Dynamics of Information in Networks Course notes - Chapter 3 Urlike Von Luxburg, A tutorial on Spectral Clustering. G. Palla, A. L. Barabasi, T. Viscek. Quantifying Social Group Evolution, Nature 2007 Lecture slides: (pptx, pdf) Lecture 6: Information Cascades, Epidemics, Influence Maximization. Game theoretic information cascade. Models for epidemic spread. Selecting influencers to maximize spread. Material: Networks, Crowds, and Markets (Chapters 9 and 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. N. Gayraud, E. Pitoura, P. Tsaparas, Diffusion Maximization in Evolving Social Networks. ACM Conference on Online Social Networks (COSN), 2015. Lecture slides: (pptx, pdf) Lecture 7: Link Analysis Ranking, Absorbing Random Walks. Web search, PageRank, HITS. Random walks on graphs. Absorbing Random Walks. Opinion diffusion. Material: Mining Massive Datasets (Chapter 10) Social Media Mining (Chapter 3) Networks, Crowds, and Markets (Chapter 14) Chapter 21 from the book "Introduction to Information Retrieval" by C. Manning, P. Raghavan, H. Schutze 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. R.Lempel, S.Moran. SALSA: The Stochastic Approach for Llink-Structure Analysis. ACM Trans. Inf. Syst.19(2):131-160 (2001) Lecture slides: (pptx, pdf) Lecture 8: Recommendation systems and Social Recommendations. Recommendation Systems and Social Recommendations. Material: Michael D. Ekstrand, John T. Riedl, Joseph A. Konstan, Collaborative Filtering Recommender Systems Mining Massive Datasets (Chapters 9,11) Social Media Mining (Chapter 9) Hao Ma, Dengyong Zhou, Chao Liu, Michael R. Lyu, Irwin King, Recommender Systems with Social Regularization, WSDM 2010 J. Tand, X. Hu. H. Liu. Social Recommendation: A Review, Social Network Analysis and Mining, 2013 David Kempe, Structure and Dynamics of Information in Networks Course notes - Chapter 4 Lecture slides: (pptx, pdf) Lecture 9: Link Prediction. Link prediction and link recommendations. Material: David Liben-Nowell, Jon Kleinberg. The Link Prediction Problem for Social Networks. J. American Society for Information Science and Technology. Ryan Lichtenwalter, Jake T. Lussier Nitesh V. Chawla. New perspectives and methods in link prediction, KDD 2010. Glen Jeh, Jenifer Widom. SimRank: A measure for sturctural context similarity. KDD 2002 Tan, Steinbach, Kumar. Introduction to Data Mining (Chapter 4) P.Gupta, A.Goel, J.Lin, A.Sharma, D.Wang, R.Zadeh. WTF:The Who to Follow Service at Twitter, WWW 2013 R.Lempel, S.Moran. SALSA: The Stochastic Approach for Llink-Structure Analysis. ACM Trans. Inf. Syst.19(2):131-160 (2001) Lecture slides: (pptx, pdf) Lecture 10: Team formation in Social Networks. Network Ties Team formation in Social Networks. Strong and Weak ties. Strong Triadic Closure. Networks with Positive and Negative ties. Structural Balance. Material: T. Lappas. K. Liu. E. Terzi, Finding a team of experts in a social network. KDD 2009 Networks, Crowds, and Markets (Chapters 3 and 5) S. Sintos, P. Tsaparas, Using Strong Triadic Closure to Characterize Ties in Social Networks. ACM International Conference on Knowledge Discovery and Data Mining (KDD), August 2014 Lecture slides: (pptx, pdf) Lecture 11: Fairness and Diversity in Social Media Formal models for fairness. Diversity in Social Media. Material: Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard Zemel. Fairness through Awareness. ITCS 2012. Marina Drosou, Evaggelia Pitoura. Search Result Diversification. SIGMOD Record 39(1), 2010. Eytan Bakshy,  Solomon Messing, and Lada A. Adamic. Exposure to Ideologically Diverse News and Opinion on Facebook. Science 348:1130–1132, 2014 Lecture slides: (pptx, pdf)