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 mathematics 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) Tutorials on Python Libraries for Data Science (from the Data Mining class) Lecture 2: Network Measurements and Models Degree distributions. Measuring power-laws. Clustering Coefficient, Effective Diameter, Bow-tie structure, Homophily. Erdos-Renyi graphs. Configuration Model. Preferential Attachment. Small-world models. Forrest-Fire model. Material: M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics. Networks, Crowds, and Markets (Chapter 3) 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 3: 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 4: 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) Signed networks with positive and negative edges. Structural Balance Networks, Crowds, and Markets (Chapters 3 and 5) Lecture slides: (pptx, pdf) Lecture 5: Link Analysis Ranking Web search, PageRank, HITS. SALSA. Random walks on graphs. 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 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 6: Epidemics. Influence Maximization. Opinion Formation models, Absorbing Random Walks. Models for epidemic spread. Selecting influencers to maximize spread. Opinion formation models. DeGroot and Friedkin-Jonhsen model. Absorbing Random Walks. Opinion maximization. Material: Networks, Crowds, and Markets (Chapterσ 3, 5 and 21) James Holland, Notes on R0 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. Christian Borgs, Michael Brautbar, Jennifer Chayes, Brendan Lucier. Maximizing Social Influence in Nearly Optimal Time. SODA 2014 Youze Tang, Xiaokui Xiao, Yanchen Shi. Influence Maximization: near-optimal time complexity meets practical efficiency. SIGMOD 2014 Wei Chen, Chi Wang, Yajun Wang. Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks. KDD 2010 Wei Chen, Yajun Wang, Siyu Yang. Efficient Influence Maximization in Social Networks. KDD 2009 Grindstead and Snell's Introduction to Probability (Chapter 11) 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. C. Castellano, S. Fortunato, V. Loreto. Statistical Physics of Social Dynamics A.Gionis, E. Terzi, P. Tsaparas. Opinion Maximization in Social Networks, SDM 2013 A. Das, S. Gollapudi, K. Munagala. Modeling opinion dynamics in Social Networks. WSDM 2014 Pawel Sobkowitz, Modeling Opinion Formation with Physics Tools. Lecture slides: (pptx, pdf) Lecture 7: Graph Machine Learning I Introduction to Graph Machine Learning. Graph Feature Engineering. Graph Kernels. The Link Prediction case Material: Nino Shervashidze et al., Efficient graphlet kernels for large graph comparison, Artificial Intelligence and Statistics, 2009 Nino Shervashidze et al., Weisfeiler-Lehman Graph Kernels, Journal of Machine Learning Research 12.9, 2011 Tijana Milenkovic, Natasa Przulj, Uncovering Biological Network Function via Graphlet Degree Signatures, Cancer Informatics, 2008, 6:257-273 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. Lecture slides: (pptx, pdf) Lecture 8: Graph Machine Learning II Introduction to Neural Networks. Graph Embeddings Material: W.L. Hamilton, R. Ying, J. Leskovec. Representation Learning on Graphs: Methods and Applications. IEEE Data Engineering Bulletin, 2017 A. Ahmed, N. Shervashidze, S. Narayanamuthy, V. Josifovski, A. J. Smola. Distributed Large-Scale Graph Factorization, WWW 2013 M. Ou, P. Cui, J. Pei, Z. Zhang, W. Zhu. Asymmetric Transitivity Preserving Graph Embedding, KDD 2016 T. Mikolov, I. Sutskever, K. Chen, G. Corrado, J. Dean. Distributed Representations of Words and Phrases and their Composionality, NIPS 2013 Chris Manning, Natural Language Processing with Deep Learning, Lecture Notes, Part I B. Perozzi, R. Al-Rfou, S. Skiena. DeepWalk: Online Learning of Social Representations, KDD 2014 A. Grover, J. Leskovec. node2vec:Scalable Feature Learning for Networks. KDD 2016 S. Cao, W. Lu, Q. Xu. GraRep: Learning Representations with Global Structure Information. CIKM 2015 Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, P. S. Yu. A Comprehensive Survey on Graph Neural Networks. Arxiv 2019 T. Kipf, M. Welling, Semi-Supervised Classification with Graph Convolutional Networks. ICLR 2017 W. Hamilton, R. Ying, J. Leskovec. Inductive Representation Learning on Large Graphs. NIPS 2017 Y. Li, R. Zemel, M. Brockschmidt, D. Tarlow. Gated Graph Sequence Neural Networks. ICLR 2016 LFR Ribeiro et. al., struc2vec Learning Node Representations from Structural Identity, KDD 2017 Dong et al., metapath2vec: Scalable Representation Learning for Heterogeneous Networks, KDD 2017 Abu-El-Haija et al., Watch Your Step: Learning Node Embeddings via Graph Attention, 2017 Tang et al., LINE: Large-scale Information Network Embedding, 2015 Chen et al., HARP: Hierarchical Representation Learning for Networks, 2016 Lecture slides: (pptx, pdf) Introduction to NNs: (pptx, pdf) Lecture 9: Graph Machine Learning IIΙ Introduction to Neural Networks. Graph Embeddings Material: A comprehensive guide to Convolutional Neural Networks J. You, R. Ying, J. Leskovec, Design Space of Graph Neural Networks, NeurIPS 2020 T. Kipf, M. Welling. Semi-supervised learning with graph convolutional networks, ICLR 2017 W. Hamilton, R. Ying, J. Leskovec, Inductive Representation Learning on Large Graphs, NeurIPS 2017 Vaswani et al., Attention is all you need, NeurIPS 2017 P. Velickovic et al., Graph Attention Networks, ICLR 2018 S. Ioffe, C. Szegedy, Batch Normalization: Accelerating Deep Network Training b y Reducing Internal Covariate Shift, ICML 2015 N. Srivastava et al., Dropout: A Simple Way to Prevent Neural Networks from Overfitting, JMLR 2014 He et al., Deep Residual Learning for Image Recognition, CVPR 2015 K. Xu et al., Representation Learning on Graphs with Jumping Knowledge Networks, ICML 2018 J. You et al., Identity-Aware Graph Neural Networks, AAAI 2021 R. Ying et al., Graph Convolutional Neural Networks for Web-Scale Recommender Systems, KDD 2018 K Xu et al., How Powerful are Graph Neural Networks?, ICLR 2019 Lecture slides: (pptx, pdf) Lecture 10: Polarization and Fairness in Networks Modeling and measuring polarization. Algorithmic Fairness. Fairness of Pagerank Material: Polarization material is mostly from the tutorial by Kiran Garimella, Gianmarco De Francisci Moralles, Michael Mathioudakis, Aristides Gionis, Polarization on Social Media, EUROCSS, 2019. You can find several references within the tutorial, some indicative ones follow Garimella et. al., Political Discourse on Social Media: Echo Chambers, Gatekeepers and the Price of Bipartisanship, WSDM 2018 Bakshy et al., Exposure to ideologically diverse news and opinions on Facebook, 2015 Guerra et al.,  A Measure of Polarization on Social Media Networks Based on Community Boundaries, ICWSM 2013 Garimella et al., Quantifying Controversy in Social Media, WSDM 2016 Matakos et al., Measuring and Moderating Polarization in Social Networks., DMKD 2017 Garimella et al., Reducing Controversy by connecting opposing views, WSDM 2017 Garimella et al., Balancing Information Exposure in Social Networks, NIPS 2017 Barocas, Hardt, Narayanam, Fairness and Machine Learning Dwork et al., Fairness through awareness, ITCS 2012 Tsioutsiouliklis et al., Fairness-aware Pagerank, WWW 2021 Tsioutsiouliklis et al., Link Recommendations for Pagerank Fairness, WWW 2022 Rahman et al., FairWalk: Towards Fair Graph Embedings, IJCAI 2019 Lecture slides: (pptx, pdf)