TA: Jae Oh Woo, in AKW 202. Usually can be found on Tues and Weds at
4:00.
 9/6/07  Lecture 1 : Introduction
Recommended reading:
I did not cover any course material in this lecture.
Rather, I gave an overview of the material that we will cover during
the course.
A list of the topics appears in the description above.
It has high overlap with the material I covered last year.
Here are the files that you need to run the demos I presented:
 9/11/07  Lecture 2 : Empirical Analyses of Graphs
Here are my notes for this lecture and my powerpoint slides.
Recommended reading:
 9/13/07  Lecture 3 : Random walks and diffusion on graphs
Here are my notes for this lecture in pdf
, and in postscript.
 9/18/07  Lecture 4 : Random walks and spectral graph drawing
Here are my notes for this lecture in pdf ,
and in postscript.
Here are files you need if you want to try the matlab examples: gplot3.m, yaleShieldBig.mat, rome.mat, erdosGraph.mat,
dodec.mat.
And, here is a paper on spectral graph drawing:
Drawing
Graphs by Eigenvectors: Theory and Practice, by Yehuda Koren.
 9/20/07  Lecture 5 : PageRank
Here are my notes for this lecture in pdf ,
and in postscript.
The readings for lecture 2 are the two fundamental papers on
web search.
 9/20/07
Problem set 1 (pdf) out, due October 4.
Here
is the postscript version.
 9/25/07  Lecture 6 : Spectral Graph Partitioning I
Here are my notes for this lecture in pdf ,
and in postscript.
What I covered differs a little from these notes.
I'll try to make up the difference in the next set of lecture notes.
Recommended reading is
 9/27/07  Lecture 7 : Spectral Graph Partitioning II
Here are my notes for this lecture in pdf ,
and in postscript.
 10/2/07, Lecture 8: Resistor Networks, Random Walks, and the
Laplacian
Recommended readings for this lecture are
Here are my notes for this lecture in pdf ,
and in postscript.
 10/4/07, Lecture 9: Resistance Distance
Here are my notes for this lecture in pdf ,
and in postscript.
Recommended readings for this lecture are
 10/5/07
Problem set 2 (pdf) out, due October
18.
Here is the postscript version.
 10/9/07, Lecture 10: Effective Resistance and Random Walks
Here are my notes for this lecture in pdf
, and in postscript.
Recommended readings for this lecture are
Other related readings are
 10/11/07, Lecture 11: Random Graphs : Markov's Inequality
Here are my notes for this lecture in pdf
, and in postscript.
 10/13/07, solving linear systems in python
I wrote some python code to demonstrate how one would create laplacians
from graphs, and then solve the resulting linear systems.
I use the SciPy package to do this.
It can take some work to get SciPy installed.
So, if you want to use it, start trying to install it soon.
 10/16/07, Lecture 12: Random Graphs : Chebyshev's Inequality
Here are my notes for this lecture in pdf.
 10/19/07
Problem set 3 (pdf) out, due November 1.
Here
is the postscript version.
 10/18/07, Lecture 13: Random Graphs : Chernoff bounds and
diameter
Here are my notes for this lecture in pdf.
 10/23/07, Lecture 14: Percolation on trees
Here are my notes for this lecture in pdf.
 10/25/07, Lecture 15: The Giant Component
Here are my notes for this lecture in pdf.
 10/30/07, Lecture 16: Percolation in the grid.
Here are my notes for this lecture in pdf.
 11/01/07, Lecture 17: Smallworld graphs.
For this lecture, I recommend reading Kleinberg's paper:
The
smallworld phenomenon: An algorithmic perspective
 11/06/07, Lecture 18: Gossip in graphs.
Here are my notes for this lecture in pdf.
This lecture was 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):25082530.
 11/08/07
Problem set 4 (pdf) out, due November 27.
Here
is the postscript version.
 11/08/07, Lecture 19: Flocking.
Here are my notes for this lecture in pdf.
Related reading:
 11/13/07, Lecture 20: KNearest Neighbor Graphs.
Related reading:
 11/15/07, Lecture 21: KNearest Neighbor Graphs and Patitioning
Geometric Graphs
Related reading:
 11/27/07, Lecture 22: Counterintuitive phenomena in networks.
Here are my notes for this lecture in pdf.
Recommended reading:
 Chapter 1 (available online) 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. 479482.
 Paradoxical
behaviour of mechanical and electrical networks
by J. E. Cohen and P. Horowitz, Nature (London) 352,
699701 (1991).
Related reading:
 11/29/07, Lecture 23: The price of anarchy.
Here are my notes for this lecture in pdf.
This lecture partially follows the lecture notes of Eva Tardos
from her classes on 9/14/05
and 9/16/05.
 11/29/07
Problem set 5 (pdf) out, due December 13.
Here
is the postscript version.
 12/04/07, Lecture 24: Clustering heuristics
 12/06/07, Lecture 25: Last lecture.
Related reading:
 A popular article on problems with sampling networks: Wanted: An Accurate
Map of the Internet, by Sara Robinson.
 Sampling
biases in IP topology measurements ,
by A Lakhina, JW Byers, M Crovella, P Xie. INFOCOM 2003.

Accuracy and Scaling Phenomena in Internet Mapping,
by A. Clauset and C. Moore. Physical Review Letters, 2005.

On the bias of traceroute sampling: or, powerlaw degree distributions
in regular graps,
by D Achlioptas, A Clauset, D Kempe, C Moore. ACM STOC 2005.
 Respondent
Driven Sampling
.

Chipfiring games on graphs, by A Bjorner, L Lovasz, PW Shor.
European Journal of Combinatorics, 1991.
 Chipfiring games on mutating graphs, by K Eriksson  SIAM J.
Discrete Math, 1996.
 Course Feedback (pdf).