T-Th 2:30 - 3:45 in DL 220 (we've moved back to DL 220)
Instructor: Dan Spielman
. Office hours Friday, 3:30-5 in AKW 201.
TFs: Xiongnan (Newman) Wu. Office hours Thurs 4-6 in AKW 311
De Wen Soh. Office hours Wednesday 4-6, in DL 509
Lectures (all claims for the future are tentative)
Aug. 29: Overview of course and introduction to some networks. (lecture notes)
Reading: Chapters 7.9 and 7.13 in detail. Chapters 2, 3.1, 3.2, 3.3, 3.4, 3.5, 4 and 5, roughly.
(diary of this lecture's Matlab session)
All the matlab code used in this, and other lectures, can be found under Resources
Reading: Sections 12.1-12-4, 12.7
Sept. 10: Heavy-tailed degree distributions, and preferential attachment models.
Sept. 17: Epidemics and Percolation on trees (PS 2 out) (lecture notes)
Reading: Sections 16.1, 17.6-17.8 (not 17.8.1).
I also recommend Chapter 4 of Probability on Trees and Networks by Lyons and Peres.
Sept. 19: Percolation in grids and real-world graphs. (lecture notes)
Sept. 24: Random Walks and Diffusion, part 1. (lecture notes)
Sept. 26: Spectral analysis of random walks . (lecture notes).
Oct. 1: Conductance and convergence of random walks. (PS 2 due) (PS 3 out) (draft of lecture notes).
Oct. 3: Personal PageRank, spilling paint and local clustering. (lecture notes).
Oct. 8: Respondent Driven Sampling and Regression on Graphs. (draft of lecture notes).
Reading on RDS:
Probability Based Estimation Theory for Respondent Driven Sampling, by Volz and Heckathorn
Sampling and Estimation in Hidden Populations Using Respondent-Driven Sampling, by Salganik and Heckathorn
Respondent-Driven Sampling: An Assessment of Current Methodology, by Gile and Handcock
Oct. 10: Physical Metaphors for Graphs. (lecture notes).
Oct. 15: Monotonicity and its Failures (PS 3 due) (draft of lecture notes).
Oct. 17: The Price of Anarchy. (lecture notes). (PS 4 out)
Oct. 22: Non-linear and dynamic networks (lecture notes).
Oct. 29: Guest lecture by Nicholas Christakis.
Oct. 31: PageRank and random walks in directed graphs. (lecture notes).
Nov. 5: An axiomatic approach to PageRank and centrality. (PS 4 due) (PS 5 out)
This lecture will be based on the paper: The PageRank Axioms, by Alon Altman and Moshe Tennenholtz.
Nov. 7: Clustering axioms and Modularity
An Impossibility Theorem for Clustering, by Jon Kleinberg
Newman, Sections 7.13, 11.2, 11.6 (but, do not trust any statements about algorithm complexity in here)
Resolution limit in community detection
Nov. 12: Spectral Clustering. (draft of lecture notes). (matlab diary)
Nov. 14: Other Clustering Heuristics (matlab diary)
Nov. 19: Link Prediction and Anomaly Detection. (PS 6 out) (lecture notes)
The Link Prediction Problem for Social Networks, by Jon Kleinberg and David Libenn-Nowell, Journal of the American Society for Information Science and Technology, Volume 58, Issue 7, pages 1019–1031, May 2007.
The Case for Anomalous Link Discovery, by Matthew J. Rattigan and David Jensen, ACM SIGKDD Explorations Newsletter, 2005
Nov. 21: Consensus in Graphs. (PS 5 due)
Randomized Gossip Algorithms, IEEE Transactions on Information Theory, 2006
The Convergence of Bird Flocking, by Bernard Chazelle,
A Lower Bound on Convergence of a Distributed Network Consensus Algorithm
Dec. 3: Belief Propagation.
Dec. 5: Random neglected topics.
Dec. 10: No class, but PS 6 due.