The flip Markov chain for connected regular graphs
The flip Markov chain for connected regular graphs
复制标题
用于连通正则图的翻转马尔可夫链
DOI：
10.1016/j.dam.2018.06.019
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Cooper C
中科院分区：
文献类型：
--
作者：
Cooper C
Mahlmann和Schindelhauer(2005)定义了一种称为k-Flipper的马尔可夫链，并证明了它在所有给定度(至少为3)的连通正则图的集合上是不可约的。研究了1-Flipper链，我们称之为Flip Chain，证明了Flipper链在n个顶点的连通2 r-正则图上快速收敛到一致分布，其中n≥8且r=r(N)≥2.形式上证明了Flipper链的分布在ε(n，r，ε−(Log 1))步长后的全变差距离一致的范围内.明确地给出了混合时间的这个多项式上界，并且显著改进了Feder等人(2006)以前给出的上界。我们通过使用我们在一般设置中定义的直接两阶段规范路径构造来实现这一改进。这项工作应用于基于偶数度随机规则连通图的去中心化网络，作为一种自稳定协议，其中节点自发地执行随机翻转以修复网络。
Mahlmann and Schindelhauer (2005) defined a Markov chain which they called k-Flipper, and showed that it is irreducible on the set of all connected regular graphs of a given degree (at least 3). We study the 1-Flipper chain, which we call the flip chain, and prove that the flip chain converges rapidly to the uniform distribution over connected 2 r-regular graphs with n vertices, where n≥ 8 and r= r (n)≥ 2. Formally, we prove that the distribution of the flip chain will be within ε of uniform in total variation distance after poly (n, r, log (ε− 1)) steps. This polynomial upper bound on the mixing time is given explicitly, and improves markedly on a previous bound given by Feder et al.(2006). We achieve this improvement by using a direct two-stage canonical path construction, which we define in a general setting. This work has applications to decentralised networks based on random regular connected graphs of even degree, as a self-stabilising protocol in which nodes spontaneously perform random flips in order to repair the network.
DOI：
--
发表时间：
2016-03
期刊：
ArXiv
影响因子：
--
作者：
V. Guruswami
通讯作者：
V. Guruswami
通过局部边缘翻转的扩展器
DOI：
10.1137/1.9781611974331.ch19
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Zeyuan Allen;Aditya Bhaskara;Silvio Lattanzi;V. Mirrokni;L. Orecchia
通讯作者：
L. Orecchia
可逆马尔可夫链的比较定理
DOI：
--
发表时间：
1993
期刊：
影响因子：
--
作者：
P. Diaconis;L. Saloff‐Coste
通讯作者：
L. Saloff‐Coste