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
Book: Networks: An Introduction, by M. E. J. Newman (available on-line through Yale Library)
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
Sept. 3: Growth of neighborhoods in random graphs. (PS 1 out) (lecture notes) (matlab diary)
Reading: Sections 12.1-12-4, 12.7
Sept. 5: Lack of community structure in random graphs. (lecture notes) (matlab diary)
Sept. 10: Heavy-tailed degree distributions, and preferential attachment models.
Reading: Sections 8.3, 8.4, 14.1, and 14.2 (lecture notes) (matlab diary)
Sept. 12: Nagivable small-world graphs. (PS 1 due) (lecture notes)
Reading: The small-world phenomenon: An algorithmic perspective, by Jon Kleinberg.
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
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
Reading:
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 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.