Graphs and Networks, Fall 2010

Applied Mathematics / Computer Science 462 / 562

T-Th 2:30-3:45 in AKW 200.

Instructor: Dan Spielman.
To make an appointment with me, follow this link Ignore the security/certificate warnings.
TFs: Chong Deng (chong.deng@yale.edu, AKW 114) and Huan Wang (huan.wang@yale.edu, AKW 202).

This is the web page for the Fall 2010 version of this class. To get a feeling for what the class is going to be like, I recommend looking at

The Fall 2007 class web page.

If you are looking for a book on graph theory, I recommend:

The on-line book by Diestel

There will be no textbook for this class. Rather, we will rely my lecture notes, and materials available on the Web. The plans for lectures that have not yet happened should be considered speculative.

Lecture 1 (Sep 2, 2010): introduction

Lecture 2 (Sep 7, 2010): empirical studies of graphs

Lectures notes in pdf (ps format). Slides.
Overview: The Structure and Function of Complex Networks, by Mark Newman. We cover Sections I, II, and II.A,B,C,F
On assortative mixing: Assortative Mixing in Networks by Mark Newman.
Graph structure in the web, by Broder et. al. You can access a nicer version from Yale machines by searching in Google Scholar.
A critique of power-law distributions for degrees: Revisiting scale-free networks by Evelyn Fox Keller.

A Brief History of Generative Models for Power Law and Lognormal Distributions (pdf) by Michael Mitzenmacher, Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
Power-law distributions in empirical data, Aaron Clauset, Cosma Rohilla Shalizi, and M. E. J. Newman, SIAM Review 51, 661-703 (2009).
Sampling Biases in IP Topology Measurements Anukool Lakhina, John W. Byers, Mark Crovella and Peng Xie, IEEE INFOCOM 2003.

Lecture 3 (Sep 9, 2010): Erdos-Renyi random graphs: warm-up

Lecture notes in pdf (ps format)

Lecture 4 (Sep 14, 2010): The Giant Component

My notes (ps) (updated 9/16/10).
Related reading: The Giant Component: The Golden Anniversary, by Joel Spencer, Notices of the AMS, vol 57 (6).

Lecture 5 (Sep 16, 2010): The diameter of random graphs with given degree distributions.

lecture notes in pdf or ps
The classic paper on the diameter of 3-regular graphs: The diameter of a cycle plus a random matching by Bollobas and Chung. SIAM Disc. Math, 1988.
Problem set 1 out. (pdf format) (ps format)

Lecture 6 (Sep 21, 2010): Navigable small-world graphs.
- This lecture will be based on the paper The small-world phenomenon: An algorithmic perspective, Proc. 32nd ACM Symposium on Theory of Computing, 2000.
- For developments after this paper, see Kleinberg's ICM 2006 paper
- For background and skepticism, I recommend Could it be a big world after all? by Judith Kleinfeld.
- So far, my lecture notes (ps) do little more than point to Kleinberg's paper.

Lecture 7 (Sep 23, 2010): Preferential attachment models of random graphs and community structure in graphs.

today's lecture notes (pdf) (ps)
matlab code for today's lecture
Today's lecture will be mostly based on the preferential attachement section of Mitzemacher's paper A Brief History of Generative Models for Power Law and Lognormal Distributions.
This paper builds on Stochastic Models for the Web Graph, (STOC '00) by Kumar, Raghavan, Rajagopalan and Sivakumar.
I may also build on the treatment in Section 18.7 of the book by Easley and Kleinberg, which builds on Barabasi and Albert's paper Emergence of Scaling in Random Networks, Science 286 (1999).

Lecture 8 (Sep 28, 2010): Random walks and diffusion.

todays lecture notes (ps)

Lecture 9 (Sep 30, 2010): Conductance and the rate of convergence.

lecture notes (ps)
Problem set 1 due.

Lecture 10 (Oct 5, 2010). The Holistic proof of convergence of random walks,

draft of lecture notes
Problem set 2 out. (pdf format) (ps)

Lecture 11 (Oct 7, 2010): PageRank and Spilling Paint

prefix of lecture notes

Lecture 12 (Oct 12, 2010): Rubber Bands and Resistor Networks

lecture notes (ps)

Lecture 13 (Oct 14, 2010): Effective Resistance.

draft of lecture notes (ps)

Lecture 14 (Oct 19, 2010): Counter-Intuitive Phenomena in Networks.

Until I get a chance to write, I recommend my notes on this topic from 2007, and the notes from the lecture of Oct 21, 2010.
Highly recommended reading: Chapter 1 (available on-line) of Selfish Routing and the Price of Anarchy by Tim Roughgarden.
What if They Closed 42d Street and Nobody Noticed?, by Gina Kolata, December 25, 1990, New York Times.
The Braess paradox in mechanical, traffic, and other networks , by C. M. Penchina and L. J. Penchina, American Journal of Physics -- May 2003 -- Volume 71, Issue 5, pp. 479-482.
Paradoxical behaviour of mechanical and electrical networks by J. E. Cohen and P. Horowitz, Nature (London) 352, 699-701 (1991).
Problem set 3 out. (pdf format) (ps)

Lecture 15 (Oct 21, 2010): The Price of Anarchy.

lecture notes (ps)
Again, I point you to my notes from 2007 on this topic
How Bad is Selfish Routing?, by T. Roughgarden and E. Tardos. JACM '02.

Lecture 16 (Oct 28, 2010): PageRank and Random Walks on Directed Graphs

lecture notes

Lecture 17 (Nov 2, 2010): The PageRank Axioms

This lecture will be based on the paper: The PageRank Axioms, by Alon Altman, Moshe Tennenholtz, which appeared in the Proceedings of the Sixth ACM Conference on Electronic Commerce.

Lecture 18 (Nov 4, 2010): Link Prediction

This lecture will be based mostly on the paper: The Link Prediction Problem for Social Networks,

Lecture 19 (Nov 9, 2010): Graph Clustering 1: Spectral and normalized.

Recommended reading: A Tutorial on Spectral Clustering, by Ulrike von Luxburg, Statistics and Computing, 17 (4), 2007.
lecture notes (ps)

Lecture 20 (Nov 11, 2010): Graph Clustering 2: Modularity.

Problem set 4 out. This is due Tuesday, Nov 30 (pdf format) (ps)

Lecture 21 (Nov 16, 2010): Gossip Algorithms.

This lecture will be based on the paper Randomized Gossip Algorithms, by S. Boyd, A. Ghosh, B. Prabhakar, D. Shah. Appeared in IEEE Transactions on Information Theory, June 2006, 52(6):2508-2530.
For now, I recommend by 2006 lecture notes on gossip.

Lecture 22 (Nov 18, 2010): Flocking.

This lecture will be mostly based on the paper A Lower Bound on Convergence of a Distributed Network Consensus Algorithm.
It will also mention the paper The Convergence of Bird Flocking, by Bernard Chazelle.
My lecture notes from 2007 for this topic are pretty good.

Lecture 23 (Nov 30, 2010): Geometric Graphs

This lecture will survey some results on percolation theory and geometric graphs.
The discussion of percolation theory will be fairly general.
The discussion of geometric graphs will be based on two papers:

k -Nearest-Neighbor Clustering and Percolation Theory, S. H Teng and F. F. Yao.
Disk Packings and Planar Separators, by Teng and myself.

Optional Problem Set 5, in pdf, due December 10, 4:00PM.

Lecture 24 (Dec 2, 2010): Last lecture.

Partial lecture notes
I will ask for feedback on this class through this form.

This material is based upon work supported by the National Science Foundation under Grant No 0915487. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).

Graphs and Networks, Fall 2010

Applied Mathematics / Computer Science 462 / 562

T-Th 2:30-3:45 in AKW 200.

Instructor: Dan Spielman. To make an appointment with me, follow this link Ignore the security/certificate warnings. TFs: Chong Deng (chong.deng@yale.edu, AKW 114) and Huan Wang (huan.wang@yale.edu, AKW 202).

Instructor: Dan Spielman.
To make an appointment with me, follow this link Ignore the security/certificate warnings.
TFs: Chong Deng (chong.deng@yale.edu, AKW 114) and Huan Wang (huan.wang@yale.edu, AKW 202).