GRAPH PARTITIONING WITH EIGENVECTORS

The Cheeger constant of a graph quantities how well a graph can be cut yield- ing two (typically) large vertex sets by a small edge cut. Lower and upper bounds have been developed using the eigenvalues and eigenvectors of the normalized Laplacian matrix of the graph. Here a classic sweep algorithm is studied using linear combinations of eigenvectors, specifically the columns of approximate discrete Green's functions. It is then shown, statistically on certain families of random graphs following a stochastic block model, that it is enough to use two eigenvalues and vectors to improve this classic algorithm's upper bound in most cases.M.S. in Applied Mathematics, May 201