An Alon-Boppana theorem for powered graphs, generalized Ramanujan graphs and robust community detection
dc.contributor.author
Abbe, Emmanuel
dc.contributor.author
Ralli, Peter
dc.contributor.editor
Lapidoth, Amos
dc.contributor.editor
Moser, Stefan M.
dc.date.accessioned
2022-03-04T12:10:17Z
dc.date.available
2022-03-04T09:30:17Z
dc.date.available
2022-03-04T12:10:17Z
dc.date.issued
2022-03-02
dc.identifier.uri
http://hdl.handle.net/20.500.11850/535272
dc.identifier.doi
10.3929/ethz-b-000535272
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zurich
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.title
An Alon-Boppana theorem for powered graphs, generalized Ramanujan graphs and robust community detection
en_US
dc.type
Conference Paper
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.book.title
International Zurich Seminar on Information and Communication (IZS 2022). Proceedings
en_US
ethz.pages.start
19
en_US
ethz.pages.end
23
en_US
ethz.event
International Zurich Seminar on Information and Communication (IZS 2022)
en_US
ethz.event.location
Zurich, Switzerland
en_US
ethz.event.date
March 2–4, 2022
en_US
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.
en_US
ethz.relation.isPartOf
10.3929/ethz-b-000534535
ethz.date.deposited
2022-03-04T09:30:22Z
ethz.source
FORM
ethz.eth
no
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2022-03-04T12:10:26Z
ethz.rosetta.lastUpdated
2022-03-29T20:10:55Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=An%20Alon-Boppana%20theorem%20for%20powered%20graphs,%20generalized%20Ramanujan%20graphs%20and%20robust%20community%20detection&rft.date=2022-03-02&rft.spage=19&rft.epage=23&rft.au=Abbe,%20Emmanuel&Ralli,%20Peter&rft.genre=proceeding&rft.btitle=International%20Zurich%20Seminar%20on%20Information%20and%20Communication%20(IZS%202022).%20Proceedings
Files in this item
Publication type
-
Conference Paper [36606]