AMTH/CPSC 462/562: Graphs and Networks

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
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) 
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 r
andom 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)

Assembly Mechanism of the Contractile Ring for Cytokinesis by Fission Yeast, Science 2007

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.