Opening Spectral Graph Theory: Linear Algebra and Irregular Graphs
Spectral Graph Theory: Linear Algebra and Irregular Graphs
- Length
- 20 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Vertex functions and the mean
Spectral graph theory on irregular graphs needs an inner product weighted by the stationary distribution of the random walk. O'Donnell starts by treating functions on vertices as random variables under , so the mean of an indicator function is the volume of a vertex set. He then gives three equivalent formulas for the variance. One is half the expected squared difference between two independent random vertices, which links global variance to the local quadratic form on edges. The -inner product scales the dot product by vertex degrees, and O'Donnell checks symmetry, linearity and non-negativity. Part of CS Theory Toolkit (CMU 15-750) at Carnegie Mellon; assumes basic linear algebra, probability and random walks.

Your comment is kept while you sign up.Sign in
Treats vertex functions as random variables under and builds a degree-weighted inner product.
Spectral graph theory on irregular graphs needs an inner product weighted by the stationary distribution of the random walk. O'Donnell starts by treating functions on vertices as random variables under , so the mean of an indicator function is the volume of a vertex set. He then gives three equivalent formulas for the variance. One is half the expected squared difference between two independent random vertices, which links global variance to the local quadratic form on edges. The -inner product scales the dot product by vertex degrees, and O'Donnell checks symmetry, linearity and non-negativity. Part of CS Theory Toolkit (CMU 15-750) at Carnegie Mellon; assumes basic linear algebra, probability and random walks.
This lecture
Lecture 41 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.