spectral clustering, Ulrike von Luxburg 2007

 

A Proof from 'The Book', Huang, Emory

A Proof from 'The Book'

https://cacm.acm.org/magazines/2020/5/244324-a-proof-from-the-book/fulltext

https://www.youtube.com/watch?v=hm9oOv-PZ6Q

By the way Huang assigned ‘-1’ for adjacency matrix, which puzzles me. 

What is exciting is that he has a theorem says that: 

    Square root of the largest degree < the largest eigen value of an Adjacency matrix < largest degree. (see a picture below)

Huang used -1 in the adjacency matrix, not the Laplacian matrix. He assumes positive and negative interactions in his graphs

 

Question: normally, zero means no interaction? 

*** spectral graph theory, clustering

https://youtu.be/8XJes6XFjxM

small eigen value indicate small bottleneck, which can be used for spectral clustering.