Expanders via Local Edge Flips
Expanders via Local Edge Flips
复制标题
通过局部边缘翻转的扩展器
DOI：
10.1137/1.9781611974331.ch19
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
L. Orecchia
中科院分区：
文献类型：
--
作者：
Zeyuan Allen;Aditya Bhaskara;Silvio Lattanzi;V. Mirrokni;L. Orecchia
设计分布式和可扩展的算法以改善网络连接是对等网络中的一个核心主题。 ），我们要设计一种分散的局部算法，该算法将图形转换为具有良好的连通性特性（低直径，膨胀等）的图，而不会影响图表的稀疏性。翻转“转换”，在每个时间步中，随机对'交换邻居'的边缘决策的随机对。但是，具有较高概率的常规扩展器图。最多可在O（N2D2 [方程] N）步骤中产生一个扩展器，我们的论点使用了基于矩阵指数的潜在功能分析，以及最新的图形不平等现象。我们还表明，我们的技术可用于分析另一个被称为“随机开关”的经过充分研究的随机过程，并表明它在O（nd）步骤中产生了一个较高概率的扩展器。
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 = Ω(log n), 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(n17d23), 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(n2d2[EQUATION] n) 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.