An Alon-Boppana theorem for powered graphs, generalized Ramanujan graphs and robust community detection
OPEN ACCESS
Loading...
Author / Producer
Date
2022-03-02
Publication Type
Conference Paper
ETH Bibliography
no
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Book title
International Zurich Seminar on Information and Communication (IZS 2022). Proceedings
Journal / series
Volume
Pages / Article No.
19 - 23
Publisher
ETH Zurich
Event
International Zurich Seminar on Information and Communication (IZS 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.
Notes
Funding
Related publications and datasets
Is part of: