Latest information:
- The template you will use for scribing is available for download here. Please add your content to the .tex file (do not modify the .sty file), compile it, and submit your .tex file and the .pdf generated to me for evaluation.
- Room change: Our lectures will now be in RLM 7.112 (and not in Jester Hall).
Problem sets:
Problem set 1 (due Tue., May 07) —
Branching processes, random graphs and phase transitions, small-world model and routing, power laws and preferential attachment
Lecture notes:
Please note that scribed notes marked as 'preliminary' have not yet been edited throughly. In addition, be aware that notes may contain typos (e-mail me if you find one).
Lecture 01 (01/15/13) —
Introduction, small-world hypothesis, Landau symbols
- Lecture notes
- Slides
- Milgram, S. (1967). The small world problem. Psychology Today, 2(1), 60-67. [pdf]
Lecture 02 (01/17/13) —
Random graphs, branching processes
Lecture 03 (01/22/13) —
Branching processes (cont'd), Chernoff bounds
Lecture 04 (01/24/13) —
Erdős-Rényi model, threshold functions
- Lecture notes
- Erdős, P., & Rényi, A. (1960). On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl, 5, 17-61. [pdf]
Lecture 05 (01/29/13) —
Second-moment method, thresholds in Erdős-Rényi model
Lecture 06 (01/31/13) —
Giant component and connectivity
Lecture 07 (02/05/13) —
Configuration model, expander graphs, weak ties, clustering, Watts-Strogratz model
- Lecture notes (preliminary)
- Granovetter, M. S. (1973). The strength of weak ties. American Journal of Sociology, 1360-1380. [pdf]
- Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature, 393(6684), 440-442. [pdf]
Lecture 08 (02/07/13) —
Decentralized routing, Kleinberg small-world model
- Lecture notes (preliminary)
- Kleinberg, J. (2000). The small-world phenomenon: an algorithm perspective. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (pp. 163-170). ACM. [pdf]
Lecture 09 (02/12/13) —
Kleinberg small-world model (cont'd)
- Lecture notes (not available)
Lecture 10 (02/14/13) —
Introduction to power laws
- Lecture notes (not available)
- Newman, M. E. (2005). Power laws, Pareto distributions and Zipf's law. Contemporary physics, 46(5), 323-351. [pdf]
Lecture 11 (02/19/13) —
Power laws (cont'd)
- Lecture notes (not available)
Lecture 12 (02/21/13) —
Preferential attachment models, Yule process
- Lecture notes (preliminary)
Lecture 13 (02/26/13) —
Node ranking, path metrics
- Lecture notes (not available)
Lecture 14 (02/28/13) —
Spectral metrics, PageRank
- Lecture notes (not available)
- Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: bringing order to the web. [pdf]
Lecture 15 (03/05/13) —
HITS algorithm, SALSA
- Lecture notes (not available)
- Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5), 604-632. [pdf]
Lecture 16 (03/07/13) —
Community detection, graph Laplacian
- Lecture notes (not available)
Lecture 17 (03/19/13) —
Spectral clustering, k-means algorithm
- Lecture notes (not available)
- Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and computing, 17(4), 395-416. [pdf]
Lecture 18 (03/21/13) —
Cut measures, relaxation and spectral clustering
- Lecture notes (not available)
Lecture 19 (03/26/13) —
Spectral clustering (cont'd), relation to random walks
- Lecture notes (not available)
Lecture 20 (03/28/13) —
Modularity maximization
- Lecture notes (not available)
Lecture 21 (04/02/13) —
TBA
- Lecture notes (not available)
Lecture 22 (04/04/13) —
TBA
- Lecture notes (not available)
Lecture 23 (04/09/13) —
Mean-field models of epidemics
- Lecture notes (not available)
Lecture 24 (04/11/13) —
SIR and Reed-Frost model
- Lecture notes (not available)
Lecture 25 (04/16/13) —
Reed-Frost model (cont'd)
- Lecture notes (not available)
Lecture 26 (04/18/13) —
SIS and fast extinction
- Lecture notes (not available)
Lecture 27 (04/23/13) —
Innovation diffusion and threshold models
- Lecture notes (not available)
- Granovetter, M. (1978). Threshold models of collective behavior. American Journal of Sociology, 1420-1443. [pdf]
Lecture 28 (04/25/13) —
Contagion on graphs
- Lecture notes (not available)
- Morris, S. (2000). Contagion. The Review of Economic Studies, 67(1), 57-78. [pdf]
Lecture 29 (04/20/13) —
General threshold and cascade models
- Lecture notes (not available)
- Kleinberg, J. (2007). Cascading behavior in networks: Algorithmic and economic issues. Algorithmic game theory, 24, 613-632. [pdf]
Lecture 30 (05/02/13) —
Optimized epidemics and submodularity
- Lecture notes (not available)
External resources:
Rights to any resource resides with the original author.- Chaintreau (Columbia)
Introduction to Social Networks, Fall 2012
[link], [notes] - Acemoglu (MIT)
Networks, Fall 2009
[link], [notes] - Kleinberg (Cornell)
The Structure of Information Networks, Spring 2011
[link], [notes] - Spielman (Yale)
Graphs and Networks, Fall 2010
[link] - Aldous (UC Berkeley)
Random Graphs and Complex Networks, Spring 2007
[link]
Advertisement:
