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

Open access
Datum
2022-03-02Typ
- Conference Paper
ETH Bibliographie
no
Altmetrics
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. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000535272Publikationsstatus
publishedBuchtitel
International Zurich Seminar on Information and Communication (IZS 2022). ProceedingsSeiten / Artikelnummer
Verlag
ETH ZurichKonferenz
Organisationseinheit
02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.
Zugehörige Publikationen und Daten
Is part of: https://doi.org/10.3929/ethz-b-000534535
ETH Bibliographie
no
Altmetrics