We will give four proofs of the Cheeger inequality which relates the eigenvalues of a graph with various isoperimetric variations of the Cheege r constant. The first is a simplified proof of the classical Cheeger inequality using eigenvectors. The second is based on a rapid mixing result for random walks by Lov\'asz and Simonovits. The third uses PageRank, a quantitative ranking of the vertices introduced by Brin and Page. The fourth proof is by an improved notion of the heat kernel pagerank. The four proofs lead to further improvements of graph partition algorithms and in particular the local partition algorithms with cost proportional to its output instead of in terms of the total size of the graph.
Copyright. All Rights Reserved.