Graphs and Networks - 2006

Applied Mathematics / Computer Science 462 / 562

Instructor: Dan Spielman. To schedule an appointment, follow the appropriate link on my homepage.

TA: Sam Daitch. Office hours: tuesday 4-5 and thursday 12:30-1:30, AKW 412.

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

• 11/30/06, Lecture 23: K-Nearest Neighbor Grapbs
  Recommended reading:
  • 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/29/06
  Undergrad Problem set 5 out, due Dec 14
  Graduate Problem set 5 out, due Dec 14

• 11/28/06, Lecture 22: Rupert's Algorithm
  This lecture closely followed the exposition on pages 548-560 the paper:
  • A Delaunary Refinement Algorithm for Quality 2-Dimensional Mesh Generation, by Jim Ruppert. Journal of Algorithms, 18(3):548-585, 1995.
    You can access this paper from computers at Yale.

• 11/16/06, Lecture 21: Delaunay Triangulations
  Recommended reading:
  • Jonathan Shewchuk's Lecture Notes, pages 9 - 16.

• 11/14/06, Lecture 20: Planar Graphs
  Here are my notes for this lecture
  Related reading.
  • Bollobas, Section I.4.
  • Disk Packings and Planar Separators, by Teng and myself.

• 11/09/06, Lecture 19: Clustering Heuristics, part II
  Here are my notes for this lecture
  Related reading.
  • Stijn van Dongen's Ph.D. Thesis: Graph Clustering by Flow Simulation
  • Unified View of Kernel k-means, Spectral Clustering and Graph Cuts, by Dhillon, Guan and Kullis
  • David Tolliver's Ph.D. Thesis: Spectral Rounding & Image Segmentation
  Here are the matlab routines I used in this lecture.
  • mclExamp.mat, contains today's test graph
  • mcldemo.m, which uses spymcl.m, viewmcl.m and mcl.m.
  • kmeans.m, which is really a demo.
  • ncutval.m.
  • plantbisection.m.
  • crudeMillerTolliver.m.
  Here are some places where you can find code for clustering and partitioning graphs.
  • MCL: Markov Clustering Algorithm
  • Graclus: graph clustering based on kernel k-means
  • METIS: a multi-level graph partitioning algorithm that we did not discuss in class. Very fast.
  • Chaco: another multi-level graph partitioning algorithm. My experience is that it is slower than METIS, but produces better partitions.
  • Scotch: I've never used this one, but it has been recommended.
  • Multiscale Normalized Cuts Segmentation Toolbox for MATLAB, by Timothee Cour, Florence Benezit and Jianbo Shi.
  • Graph Analysis Toolbox matlab code, by Leo Grady (based on electrical flow). Also, look at the software section of Grady's web page.

• 11/09/06
  Undergrad Problem set 4 out, due Nov 28
  Graduate Problem set 4 out, due Nov 28

• 11/08/06
  Instructions for Class Projects (For those who choose to do them).

• 11/07/06, Lecture 18: Clustering Heuristics, part I
  Here are my notes for this lecture
  

  You can find the papers related to today's lecture by a simple web search.

  Here are some of the matlab files that I used or created in this class.

  • nov7.mat, contains the point set and graph
  • primdemo.m, demo of single-link clustering
  • prim.m, Prim's algorithm for comuting minimum spanning trees
  • prdemo.m, demo of personal pagerank
  • mcl.m, crude version of mcl algorithm
  • plotmcl.m, draw pictures of components produced by mcl
  • comps.m, find connected components in a graph, used by plotmcl

• 11/02/06, Lecture 17: Diameters of Random Graphs
  Here are my notes for this lecture
  

• 10/31/06, Lecture 16: Empirical Analyses of Graphs, I
  Here are my notes for this lecture
  Recommended reading:
  • Pages 4-19 from The Structure and Function of Complex Networks, by Mark Newman.

• 10/26/06, Lecture 15: Random Graphs, IV: The Giant Component
  Here are my notes for this lecture

• 10/25/06
  Undergrad Problem set 3 out, due in two weeks
  Graduate Problem set 3 out, due in two weeks

• 10/24/06, Lecture 14: Random Graphs, III: The Giant component
  Here are my notes for this lecture
  
  • David Gleich's Giant Component Demo
  • Amin Saberi's lecture notes on this topic.

• 10/19/06, Lecture 13: Random Graphs, II
  Here are my notes for this lecture
  Recommended reading:
  • Alistair Sinclair's lecture notes on this topic.

• 10/17/06, Lecture 12: Random Graphs, I
  Here are my notes for this lecture
  Recommended reading:
  • Graph Theory, by Diestel, Sections 11.1 through 11.2.

• 10/12/06, Lecture 11: Percolation, II
  Here are my notes for this lecture
  
  • Dana Randall's lecture notes on this topic.

• 10/11/06
  Undergrad Problem set 2 out, due in two weeks
  Graduate Problem set 2 out, due in two weeks

• 10/10/06, Lecture 10: Percolation, I
  Here are my notes for this lecture
  Recommended reading:
  • Chapter 1, through Section 1.3, of the lecture notes for Models and Methods for Random Networks, by Grossglauser and Thiran.

• 10/05/06, Lecture 9: Gossip in Graphs
  Here are my notes for this lecture
  Recommended reading:
  • 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.

• 10/03/06, Lecture 8: The Electrical Connection, part II
  The lecture came from
  • Bollobas, pp. 298-309.
  • Random Walks for Image Segmentation, by Leo Grady, accepted to IEEE Trans. on Pattern Analysis and Machine Intelligence, 2006.

• 9/28/06, Lecture 7: The Electrical Connection, part I
  Here are my notes for this lecture
  Recommended reading for this and Lecture 8 is
  • In Bollobas, Sections II.1, IX.1 and IX.2.
  • 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.

• 9/26/06, Lecture 6: Spectral Partitioning and Image Segmentation
  Here are my notes for this lecture
  Undergrad Problem set 1 out, due in two weeks
  Graduate Problem set 1 out, due in two weeks

  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.
  • In Bollobas, Section IX.4, through the statement of Theorem 27. Also, the statement of Corollary 31.
  • 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.
  Here are some of the matlab files that I used or created in this class.
  • airplane.JPG, imgeig.m, amdSolveF.m, lupSolveF.m, lupSolve.m, sparsecut.m, imcut.m.

• 9/21/06, Lecture 5: Spectra of some graphs.
  Here are my notes for this lecture
  Recommended reading is
  • the notes from the second lecture of my Spectral Graph Theory Course, even though they are dealing with the Laplacian matrix instead of the walk matrix. The techniques used will be very similar.
  Here are some of the matlab files that I used or created in this class.
  • art3.m, dodec, erdosGraph.mat, rome.mat, grid2.m.

• 9/19/06. Lecture 4: Random Walks
  Here are my notes for this lecture, and here is an example I did in class.
  Recommended reading is
  • In, Random Walks on Graphs: A Survey, by L. Lovasz, Section 0, Section 1, Section 2 through example 1, Section 3 (pages 14 and 15) and Section 5(pages 23-25).

• 9/14/06. Lecture 3: PageRank 2.
  Here are my notes for this lecture
  This lecture is based on two papers. They are
  • The Measurement of Intellectual Influence, by Ignacio Palacios-Huerta and Oscal Volij, Econometrica, Vol. 72, No. 3 (May 2004) 963-977.
    You can find this paper by searching for Econometrica at the Library's Online Journals Page
  • The PageRank Axioms, by Alon Altman, Moshe Tennenholtz, which appeared in the Proceedings of the Sixth ACM Conference on Electronic Commerce.
    This is a link to the conference version, and this is a link to a more complete version

• 9/12/06. Lecture 2: PageRank 1.
  Here are my notes for this lecture
  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/07/06. Lecture 1: Introduction.
  The reading for this lecture is in Bollobas, from page 1 through Corollary 9. This will provide essential background on graph theory.

• Course Description