Expander graphs and graph partitioning

10/27/2015 - 12:15pm
10/27/2015 - 1:10pm
Blake Hunter (CMC)

Expander graphs are widely used in Computer Science and Mathematics. A graph is expanding if the second eigenvalue of the standard random walk on this graph is bounded away from 1 (equivalently, the smallest eigenvalue of the Laplacian is strictly larger than 0). Graph partitioning has recently gained popularity in computer vision (clustering) and in network analysis (community detection) because if it’s ability to gain latent knowledge of a system given no prior information. Spectral clustering is a graph partitioning method that uses the eigenvector corresponding to the smallest eigenvalue of the graph Laplacian (or the second largest eigenvalue of the standard random walk). This talk will explore the surprising connections between expander graphs and graph partitioning.

Millikan 2099, Pomona College