Graphs and Networks, Fall 2007

Applied Mathematics / Computer Science 462 / 562

Instructor: Dan Spielman. Office hours Friday 2-4.

TA: Jae Oh Woo, in AKW 202. Usually can be found on Tues and Weds at 4:00.

T-Th 2:30-3:45 in ML 211. ClassesV2 page for this class

• The Fall 2006 class web page.

• The on-line book by Diestel

Lectures

• 9/6/07 - Lecture 1 : Introduction
  Recommended reading:
  • Course description

  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:
  • sep6a.m: The spectral graph drawing demo. Press any key after the first image comes up.
  • sep6b.m: Making a graph from an image.
  • seggui.m: Run seggui(img) if you just ran sep6b to segment that image. Click on two points, then select "segment" from the segmentation menu.
  • The other files you need are: airplane.JPG amdSolveF.m imcut.m imgFlowSep.m imgPoints.m imgseg3.m lupSolveF.m lupSolve.m sparsecut.m

• 9/11/07 - Lecture 2 : Empirical Analyses of Graphs
  Here are my notes for this lecture and my powerpoint slides.

  Recommended reading:

  • Overview: Pages 1-14 from The Structure and Function of Complex Networks, by Mark Newman.
  • On assortative mixing: Mixing patterns in networks, by Mark Newman.
  • Graph structure in the web, by Broder et. al.
  • A critique of power-law distributions for degrees: Revisiting scale-free networks by Evelyn Fox Keller.
  • A popular article on problems with sampling networks: Wanted: An Accurate Map of the Internet, by Sara Robinson.

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

  • The first is Authoritative sources in a hyperlinked environment, by Jon Kleinberg Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.

  • The second is, The PageRank Citation Ranking: Bringing Order to the Web, by Page, Lawrence; Brin, Sergey; Motwani, Rajeev; Winograd, Terry. Stanford University CS Tech Report 1999-66

• 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

  • Normalized Cuts and Image Segmentation, by Jianbo Shi and Jitendra Malik, in IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI), 2000. You can safely skip the uglier mathematical derivations.
  • The paper "New Spectral Methods for Ratio Cut Partitioning and Clustering" by Hagen and Kahng, IEEE Transactions on Computer-Aided Design, vol 11., no. 9, Sept 1992.

• 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.
  • Pages 30-54 in Random Walks and Electric Networks, by Doyle and Snell.
  • Pages 18-36 inProbability on Trees and Networks by Lyons and Peres.
  • Random Walks for Image Segmentation, by Leo Grady, IEEE Transactions on Pattern Analysis and Machine Intelligence ,vol. 28, no. 11, pp. 1768-1783, November, 2006.

• 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

  • Resistance Distance, by Klein and Randic. Journal of Mathematical Chemistry 12 (1993)81-95.

• 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

  • Pages 42-55 in Random Walks and Electric Networks, by Doyle and Snell.
  • Theorem 2.1 of The electrical resistance of a graph captures its commute and cover times, by Chandra, Raghavan, Ruzzo, Smolensky and Tiwari.
  Other related readings are
  • Graph Nodes Clustering based on the Commute-Time Kernel, by Yen, Fouss, Decaestecker, Francq and Saerens
  • Random-walk computation of similarities between nodes of a graph, with application to collaborative recommendation, by Fouss, Pirotte, Renders and Saerens

• 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.
  • My python code
  • A transcript of my python session
• 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: Small-world graphs.
  For this lecture, I recommend reading Kleinberg's paper: The small-world 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):2508-2530.

• 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:

  • Coordination of groups of mobile autonomous agents using nearest neighbor rules, by A. Jadbabaie, J. Lin and A. S. Morse.
  • A Lower Bound on Convergence of a Distributed Network Consensus Algorithm, by M. Cao, A. S. Morse and D. A. Spielman.

• 11/13/07, Lecture 20: K-Nearest Neighbor Graphs.
  

  Related reading:

  • Interaction Ruling Animal Collective Behaviour Depends on Topological rather than Metric Distance: Evidence from a Field Study, Ballerini, et. al.
  • Section 3.2 of Separators for sphere-packings and nearest neighbor graphs by Miller, Teng, Thurston and Vavasis. Journal of the ACM, Volume 44 , Issue 1 (January 1997).
    You can access this from any Yale computer.

• 11/15/07, Lecture 21: K-Nearest Neighbor Graphs and Patitioning Geometric Graphs
  

  Related reading:

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

• 11/27/07, Lecture 22: Counter-intuitive phenomena in networks.
  Here are my notes for this lecture in pdf.

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

  Related reading:
  • How Bad is Selfish Routing?, by T. Roughgarden and E. Tardos. JACM '02.

• 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, power-law degree distributions in regular graps, by D Achlioptas, A Clauset, D Kempe, C Moore. ACM STOC 2005.
  • Respondent Driven Sampling .
  • Chip-firing games on graphs, by A Bjorner, L Lovasz, PW Shor. European Journal of Combinatorics, 1991.
  • Chip-firing games on mutating graphs, by K Eriksson - SIAM J. Discrete Math, 1996.

• Course Feedback (pdf).