Home
Homework
Slides
& References
Reading
Material
Resources
|
Lecture 1: Introduction
Introduction
to main problems about networks. Basic mathematics
concepts
Material:
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.
- Part II, Chapters
6,9, and Part IV from The Atlas for
the Aspiring Network Scientist
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 -
Signed Networks
Graph Partitioning, Spectral
Clustering. The Densest Subgraph problem.
Material:
Lecture
slides: (pptx, pdf)
Signed networks with positive and negative edges.
Structural Balance
Lecture
slides: (pptx, pdf)
Lecture 6: Epidemics. Influence Maximization.
Models for epidemic spread.
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
Lecture
slides: (pptx, pdf)
Lecture 7: Opinion
Formation models, Absorbing Random Walks. Strong and
Weak ties.
Selecting influencers
to maximize spread. Opinion formation models. DeGroot
and Friedkin-Jonhsen model. Absorbing Random
Walks. Opinion maximization.
Material:
- 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)
Strong
and Weak ties. Strong Triadic Closure.
Material:
Lecture slides: (pptx, pdf)
|