Opening Spectral Graph Theory: The Laplacian and the Spectral Theorem
Spectral Graph Theory: The Laplacian and the Spectral Theorem
- Length
- 38 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: The Laplacian matrix
The normalized Laplacian of a graph is defined as the identity minus the random walk operator, and O'Donnell motivates it from its quadratic form. Applied to a function at a vertex, the Laplacian gives the difference between the function's value and the average over its neighbours. For regular graphs it is related to the unnormalized Laplacian. The quadratic form measures cut size, which leads to conductance as the escape probability of a random walk and to the sparsest cut problem. Maximizing the quadratic form under a norm constraint yields an eigenvector relation, and repeating this over orthogonal subspaces proves the Spectral Theorem: an orthonormal basis of real eigenvectors. Lecture 14b of CMU 15-750, A Theorist's Toolkit, assuming linear algebra, basic probability and graph definitions.

Your comment is kept while you sign up.Sign in
Builds the normalized Laplacian from its quadratic form and proves the Spectral Theorem by successive maximization.
The normalized Laplacian of a graph is defined as the identity minus the random walk operator, and O'Donnell motivates it from its quadratic form. Applied to a function at a vertex, the Laplacian gives the difference between the function's value and the average over its neighbours. For regular graphs it is related to the unnormalized Laplacian. The quadratic form measures cut size, which leads to conductance as the escape probability of a random walk and to the sparsest cut problem. Maximizing the quadratic form under a norm constraint yields an eigenvector relation, and repeating this over orthogonal subspaces proves the Spectral Theorem: an orthonormal basis of real eigenvectors. Lecture 14b of CMU 15-750, A Theorist's Toolkit, assuming linear algebra, basic probability and graph definitions.
This lecture
Lecture 44 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.