Home
Homework
Slides
& References
Reading
Material
Resources
|
Lecture 1: Introduction
Introduction
to main problems about networks. Basic mathematic
concepts
Material:
Lecture
slides (pptx,
pdf).
Introduction to Graph Theory (pptx,
pdf)
(slides from Social Media
Mining)
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: Link Analysis Ranking
Web
search, PageRank, HITS. SALSA. Random walks
on graphs.
Material:
Lecture slides: (pptx, pdf)
Lecture 4: Community Detection
Communities
in Social Networks, Clustering, Betweeness, Modularity
Material:
Lecture slides: (pptx, pdf)
Lecture 5: Graph Partitioning, Densest Subgraph
Graph
Partitioning, Spectral
Clustering. The Densest Subgraph problem.
Material:
Lecture slides: (pptx, pdf)
Lecture 6: Epidemics.
Models for epidemic spread.
Material:
Lecture slides: (pptx, pdf)
Lecture 7: Influence
Maximization. Opinion Formation models, Absorbing
Random Walks. Positive and Negative ties.
Selecting influencers to
maximize spread. Opinion formation models. DeGroot
and Friedkin-Jonhsen model. Absorbing Random
Walks. Opinion maximization. Networks
with Positive and Negative ties. Structural Balance.
Material:
- 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 8: Link Prediction.
Link prediction and link recommendations.
The SimRank algorithm.
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 9: Graph
Embeddings
Representation
Learning on Graphs. Graph Embeddings. Neural
Networks. Graph Neural Networks.
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
Lecture slides: (pptx, pdf)
Lecture
10: Fairness and Diversity in Social Media
Formal
models for fairness. Diversity in Social
Media.
Material:
Lecture slides: (pptx, pdf)
|