Seminars & Colloquia Calendar
Graph Powering and Spectral Robustness
Peter Ralli (Princeton)
Location: Hill 705
Date & time: Monday, 28 October 2019 at 2:00PM - 3:00PM
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.