1. Expanders via local edge flips in quasilinear time
- Author
-
Giakkoupis, George, the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), ANR-20-CE25-0002,ByBloS,Au-delà des Blockchains : Modules de construction pour les applications à grande échelle zero-confiance multi-utilisateurs(2020), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), and ANR-16-CE23-0016,PAMELA,Apprentissage automatique décentralisé et personnalisé sous contraintes(2016)
- Subjects
[INFO]Computer Science [cs] - Abstract
International audience; Mahlmann and Schindelhaue [24] proposed the following simple process, called flip-chain, for transforming any given connected d-regular graph into a d-regular expander: In each step, a random 3-path abcd is selected, and edges ab and cd are replaced by two new edges ac and bd, provided that ac and bd do not exist already. A motivation for the study of the flip-chain arises in the design of overlay networks, where it is common practice that adjacent nodes periodically exchange random neighbors, to maintain good connectivity properties. It is known that the flip-chain converges to the uniform distribution over connected d-regular graphs, and it is conjectured that an expander graph is obtained after O(nd log n) steps, w.h.p., where n is the number of vertices. However, the best known upper bound on the number of steps is O(n^2 d^2 √ log n) [1], and the best bound on the mixing time of the chain is O(n^16 d^36 log n) [11, 6]. We provide a new analysis of a natural flip-chain instantiation, which shows that starting from any connected d-regular graph, for d = Ω(log^2 n), an expander is obtained after O(nd log^2 n) steps, w.h.p. This result is tight within logarithmic factors, and almost matches the conjectured bound. Moreover, it justifies the use of edge flip operations in practice: for any d-regular graph with d = poly(log n), an expander is reached after each vertex participates in at most poly(log n) operations, w.h.p. Our analysis is arguably more elementary than previous approaches. It uses the novel notion of the strain of a cut, a value that depends both on the crossing edges and their adjacent edges. By keeping track of the cut strains, we form a recursive argument that bounds the time before all sets of a given size have large expansion, after all smaller sets have already attained large expansion.
- Published
- 2022
- Full Text
- View/download PDF