Spectral Graph Theory For Dummies

Video Description

To try everything Brilliant has to offer—free—for a full 30 days, visit https://brilliant.org/Ron . You’ll also get 20% off an annual premium subscription. This video was sponsored by Brilliant. --- References: 1. Cornell University Lecture Note: https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture7.pdf 2. Spectral Graph Theory Lecture by Steve Butler: https://www.stevebutler.org/spectral2023 3. Spectral Graph Theory Lecture by Radu Horaud: https://csustan.csustan.edu/~tom/Clustering/GraphLaplacian-tutorial.pdf 4. Tutorial by Daniel A. Spielman: https://www.cs.cmu.edu/afs/cs/user/glmiller/public/Scientific-Computing/F-11/RelatedWork/Spielman/SpectTut.pdf 5. This Stack Exchange question: https://stats.stackexchange.com/questions/459640/why-eigenvectors-reveal-the-groups-in-spectral-clustering 6. And this Quora question: https://www.quora.com/Whats-the-intuition-behind-a-Laplacian-matrix-Im-not-so-much-interested-in-mathematical-details-or-technical-applications-Im-trying-to-grasp-what-a-laplacian-matrix-actually-represents-and-what-aspects-of-a-graph-it-makes-accessible --- Timestamp: 0:00 Introduction 0:30 Outline 00:57 Review of Graph Definition and Degree Matrix 03:34 Adjacency Matrix Review 05:03 Review of Necessary Linear Algebra 09:09 Introduction of The Laplacian Matrix 15:36 Why is L called the Laplace Matrix 18:14 Eigenvalue 0 and Its Eigenvector 20:27 Fiedler Eigenvalue and Eigenvector 23:56 Sponsorship Message 25:02 Spectral Embedding 25:38 Spectral Embedding Application: Spectral Clustering 27:51 Outro ​ --- Big thanks to professor Fan Chung Graham and professor Robert Ellis for the email conversations.