Graphs and Networks, Fall 2010
Applied Mathematics / Computer Science 462 / 562
T-Th 2:30-3:45 in AKW 200.
To make an appointment with me, follow this link
Ignore the security/certificate warnings.
TFs: Chong Deng (email@example.com, AKW 114) and Huan Wang
(firstname.lastname@example.org, 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
If you are looking for a book on graph theory, I recommend:
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
Here are more references on power laws:
by Michael Mitzenmacher, Internet
vol 1, No. 2, pp. 226-251, 2004.
empirical data, Aaron Clauset, Cosma Rohilla Shalizi, and
M. E. J. Newman, SIAM Review 51, 661-703 (2009).
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 4 (Sep 14, 2010): The Giant Component
- Lecture 5 (Sep 16, 2010): The diameter of random graphs with
given degree distributions.
- Lecture 6 (Sep 21, 2010): Navigable small-world graphs.
- Lecture 7 (Sep 23, 2010): Preferential attachment models of
random graphs and community structure in graphs.
- Lecture 8 (Sep 28, 2010): Random walks and diffusion.
- Lecture 9 (Sep 30, 2010): Conductance and the rate of convergence.
- Lecture 10 (Oct 5, 2010). The Holistic proof of convergence of
- 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
- 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.
Noticed?, by Gina Kolata,
December 25, 1990, New York Times.
, by C.
M. Penchina and L. J. Penchina, American Journal of Physics -- May 2003
-- Volume 71, Issue 5, pp. 479-482.
by J. E. Cohen and P.
Horowitz, Nature (London) 352,
- Problem set 3 out. (pdf format) (ps)
- Lecture 15 (Oct 21, 2010): The Price of Anarchy.
- Lecture 16 (Oct 28, 2010): PageRank and Random Walks on Directed
- 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
- Lecture 18 (Nov 4, 2010): Link Prediction
- This lecture will be based mostly on the paper:
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
- Lecture 20 (Nov 11, 2010): Graph Clustering 2: Modularity.
- Lecture 21 (Nov 16, 2010): Gossip Algorithms.
- Lecture 22 (Nov 18, 2010): Flocking.
- Lecture 23 (Nov 30, 2010): Geometric Graphs
- This lecture will survey some results on percolation theory and
- The discussion of percolation theory will be fairly general.
- The discussion of geometric graphs will be based on two papers:
- Optional Problem Set 5, in pdf, due December 10, 4:00PM.
- Lecture 24 (Dec 2, 2010): Last lecture.
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).