Random Walks on Directed Graphs
summary
Defines a symmetric normalized Laplacian via Perron vector for a directed transition matrix and proves Cheeger-type bounds: the spectral gap controls cut conductance and mixing but picks up a log(1/min phi) factor because stationary mass can be exponentially small. Extends to higher-order Cheeger via expander partition using a weaker Rayleigh characterization and a Luca–Shayan style partition into L expanders, yielding multiway cut guarantees and discrepancy inequalities for edge flows weighted by the stationary distribution. Provides one-page proofs and notes open combinatorial gaps.
AI-written summary · about
chapters (14)
- 0:00Directed graph challenges
- 2:04Eigenvalues and random walks
- 3:35Outline of graph analysis
- 5:24Laplacian and spectral gap
- 7:45Isoperimetric constants
- 9:30Cheeger inequalities
- 12:01Proof of Cheeger inequality
- 15:30Higher-order inequalities
- 18:18Proof of higher-order
- 22:15Directed graph properties
- 26:31Directed Cheeger constant
- 29:10Directed Rayleigh quotient
- 34:08Spectral bounds and convergence
- 37:22Quasi-randomness and future work
related talks
01h 05mRandom Walks on Simplicial Complexes for Exploring Networks
49mExtremal Cuts of Sparse Random Graphs
01h 02mGraph Powering
01h 04mHigher-dimensional Expansion of Random Geometric Complexes
49mRecent Advances in Counting Sparse Graphs
01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IV
49mGeneralized Cheeger Inequalities and Constrained Clustering
01h 17mPedagogical Talk: Random Optimisation Problems