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).

- 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.

Here are more references on power laws:

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

- 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.

- 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

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

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

- 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

Related reading:
- 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 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,
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 - 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.