Peter Ralli, Princeton University

Abstract

Given an original graph G and positive integer r, graph powering produces a graph connecting vertices from the original graph that are within distance r.  I will discuss the use of graph powering for spectral clustering: in a sparse graph the spectrum of the adjacency matrix might be contaminated by non-informational top eigenvalues.  It is shown that graph powering regularizes the graph and decontaminates its spectrum in the following sense: if the graph is drawn from the sparse Erdős-Rényi ensemble, which has no spectral gap, it is shown that graph powering produces a `maximal' spectral gap, which is justified by establishing an Alon-Boppana result for powered graphs. 

Joint works with E. Abbe, E. Boix, and C. Sandon