Spectral Graph Theory and PageRank

From the creator

From the Columbia Mathematics Summer 2014 Undergraduate Research Project. Classical results in spectral graph theory show that an eigenvector for the Laplacian matrix associated to a graph can be used to find sparse cuts, i.e. subsets of the graph with many more internal edges than external edges. In recent years there has been considerable interest in finding locally computable approaches to the sparse cutting problem; one of the most successful techniques is based on Google's PageRank algorithm. In this talk we will explore how these tools can be adapted to analyze dense cuts in graphs, i.e. subsets with many more external edges than internal edges. Riaz Helfer, Anish King, Samuel Nicoll, and Robert Shorb (advised by Paul Siegel and Thomas Nyberg)

Published 2014-09-02 · Watch on YouTube ↗
Availability and playback restrictions are controlled by the original channel.