Opening Spectral Graph Theory: The Markov Transition Operator
Spectral Graph Theory: The Markov Transition Operator
- Length
- 41 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 5: Spectral graph theory basics
O'Donnell proves the neighbor-averaging operator is self-adjoint and shows computes -step random walk averages.
The Markov transition operator , or normalized adjacency matrix, anchors the second part of O'Donnell's treatment of spectral graph theory in CMU 15-750, A Theorist's Toolkit. He begins with functions on the vertices of an undirected graph, using an inner product weighted by the stationary distribution. The quadratic form returns as a measure of how a function varies across edges, linking linear algebra to graph cuts. O'Donnell then defines as neighbor averaging, identifies it as a stochastic matrix, and proves its self-adjointness through random edges. Powers give expectations after -step random walks; linear algebra, basic probability and graph terminology are assumed.
The Markov transition operator , or normalized adjacency matrix, anchors the second part of O'Donnell's treatment of spectral graph theory in CMU 15-750, A Theorist's Toolkit. He begins with functions on the vertices of an undirected graph, using an inner product weighted by the stationary distribution. The quadratic form returns as a measure of how a function varies across edges, linking linear algebra to graph cuts. O'Donnell then defines as neighbor averaging, identifies it as a stochastic matrix, and proves its self-adjointness through random edges. Powers give expectations after -step random walks; linear algebra, basic probability and graph terminology are assumed.

This lecture
Lecture 43 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.
Your comment is kept while you sign up.Sign in