Expanders via local edge flips

DOI10.1137/1.9781611974331.CH19zbMATH Open1410.68271arXiv1510.07768OpenAlexW2949352163MaRDI QIDQ4575596FDOQ4575596

Authors: Zeyuan Allen Zhu, Aditya Bhaskara, Silvio Lattanzi, Lorenzo Orecchia, Vahab S. Mirrokni 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: Designing distributed and scalable algorithms to improve network connectivity is a central topic in peer-to-peer networks. In this paper we focus on the following well-known problem: given an $n$-node $d$-regular network for $d=Omega(logn)$, we want to design a decentralized, local algorithm that transforms the graph into one that has good connectivity properties (low diameter, expansion, etc.) without affecting the sparsity of the graph. To this end, Mahlmann and Schindelhauer introduced the random "flip" transformation, where in each time step, a random pair of vertices that have an edge decide to `swap a neighbor'. They conjectured that performing $O(nd)$ such flips at random would convert any connected $d$-regular graph into a $d$-regular expander graph, with high probability. However, the best known upper bound for the number of steps is roughly $O(n^{17}{d}^{23})$, obtained via a delicate Markov chain comparison argument. Our main result is to prove that a natural instantiation of the random flip produces an expander in at most $O(n^2{d}^{2}sqrtlogn)$ steps, with high probability. Our argument uses a potential-function analysis based on the matrix exponential, together with the recent beautiful results on the higher-order Cheeger inequality of graphs. We also show that our technique can be used to analyze another well-studied random process known as the `random switch', and show that it produces an expander in $O(nd)$ steps with high probability.

Full work available at URL: https://arxiv.org/abs/1510.07768

Recommendations

• The flip Markov chain for connected regular graphs
• The flip Markov chain and a randomising P2P protocol
• Expansion properties of a random regular graph after random vertex deletions
• Expanders via random spanning trees
• Expansion and Lack Thereof in Randomly Perturbed Graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)

Cited In (5)

• A triangle process on regular graphs
• Expansion and flooding in dynamic random networks with node churn
• Expanders via local edge flips in quasilinear time
• The flip Markov chain and a randomising P2P protocol
• The flip Markov chain for connected regular graphs

This page was built for publication: Expanders via local edge flips

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575596)