The switch Markov chain for sampling irregular graphs (Extended Abstract)
The switch Markov chain for sampling irregular graphs (Extended Abstract)
复制标题
用于采样不规则图的开关马尔可夫链（扩展摘要）
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Catherine S. Greenhill
中科院分区：
文献类型：
--
作者：
Catherine S. Greenhill
从给定度序列的一组（无向）图中有效采样的问题有许多应用。解决这个问题的一种方法是使用一个简单的马尔可夫链，我们称之为开关链，来执行抽样。已知开关链对于正则度序列是快速混合的。证明了对于最小度≥1且最大度$d_{\max}$满足$3\leq d_{\max}\leq \frac{1}{4}\, \sqrt{M}$的任意度序列，开关链是快速混合的，其中$M$为度的和。得到的混合时间范围仅比常规情况下建立的时间范围大一个数量级$n$，其中$n$为顶点数。
The problem of efficiently sampling from a set of(undirected) graphs with a given degree sequence has many applications. One approach to this problem uses a simple Markov chain, which we call the switch chain, to perform the sampling. The switch chain is known to be rapidly mixing for regular degree sequences. We prove that the switch chain is rapidly mixing for any degree sequence with minimum degree at least 1 and with maximum degree $d_{\max}$ which satisfies $3\leq d_{\max}\leq \frac{1}{4}\, \sqrt{M}$, where $M$ is the sum of the degrees. The mixing time bound obtained is only an order of $n$ larger than that established in the regular case, where $n$ is the number of vertices.