An Alon-Boppana theorem for powered graphs, generalized Ramanujan graphs and robust community detection

Abstract

Motivated by the problem of robust community detection, we study the r-th power of a graph, i.e., the new graph obtained by connecting every vertex pair in the original graph within distance r. This paper gives a generalization of the Alon-Boppana Theorem for the r-th power of graphs, including irregular graphs. This leads to a generalized notion of Ramanujan graphs, those for which the powered graph has a spectral gap matching the derived Alon-Boppana bound. In particular, we show that certain graphs that are not good expanders due to local irregularities, such as Erdos-Rényi random graphs, become ˝ almost Ramanujan once powered. A different generalization of Ramanujan graphs can also be obtained from the nonbacktrack ing operator. We next argue that the powering operator gives a more robust notion than the latter: Sparse Erdos-Rényi random ˝ graphs with an adversary modifying a subgraph of log(n) ε vertices are still almost Ramanujan in the powered sense, but not in the nonbacktracking sense. As an application, this gives robust community testing for different block models.