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, 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. 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 (pptx, pdf) Lecture 4: Graph Partitioning, Community Detection Communities in Social Networks, Centrality and Betweeness, Graph Partitioning. 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 Lecture slides: (pptx, pdf) Lecture 6: 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. Lecture slides: (pptx, pdf) Lecture 7: 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. Lecture slides: (pptx, pdf) Lecture 8: Strong and Weak Ties, Structural Balance Strong and Weak ties. Affiliation networks. Networks with Positive and Negative ties. Structural Balance. Material: Networks, Crowds, and Markets (Chapters 3,4 and 5) 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) Lecture slides: (pptx, pdf) Lecture 10: Recommendation Systems. Recommendation Systems, Collaborative Filtering, Group Recommendations, Social Recommendations Material: 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 David Kempe, Structure and Dynamics of Information in Networks Course notes - Chapter 4 Lecture slides: (pptx, pdf) Lecture 11: Mining Social Content. Using content from online social networks and media to predict stock changes, track earthquakes, and understand news cycles. Material: Eduardo J. Ruiz, Vaggelis Hristidis, Carlos Castillo, Aristides Gionis, Alejandro Jaimes, Correlating Financial Time Series with Micro-Blogging Activity, WSDM 2012. Takeshi Sakaki, Makoto Ozakaki, Yutaka Matsuo, Earthquake shakes Twitter users: Real-time event detection by social sensors, WWW 2010. Jure Leskovek, Lars Backstorm, Jon Kleinberg, Meme-tracking and the dynamics of the news cycle, KDD 2009 Lecture slides: (pptx, pdf)