论文标题
近似图形的近似$ P $稳定度间隔
Approximate Sampling of Graphs with Near-$P$-stable Degree Intervals
论文作者
论文摘要
具有给定学位序列的图形实现的近似统一抽样是几个社会科学，计算机科学，工程等项目的日常任务。一种方法是使用马尔可夫链。关于良好的开关马尔可夫链的最佳当前结果是它正在以p稳定度序列迅速混合（请参阅doi：10.1016/j.ejc.2021.103421）。开关马尔可夫链不会改变任何度序列。但是，在某些情况下，指定度间隔而不是单度序列。 （在仅部分观察到的社交网络上的假设测试中，出现的自然情况是。）Rechner，Strowick和Müller-Hannemann在2018年在2018年介绍的Markov链的概念，使用了三个（分别研究了）本地操作（切换，铰链挡板和拨动），并在级别上进行了较小的序列范围。最近，Amanatidis和Kleer发表了一篇精美的论文（Arxiv：2110.09068），表明，如果序列来自一个非常薄的间隔系统，该学位间隔Markov链正在迅速混合，而这些序列远非正常程度序列。在本文中，我们大大扩展了它们的结果，表明如果间隔以p稳定度序列为中心，则程度间隔马尔可夫链正在迅速混合。
The approximate uniform sampling of graph realizations with a given degree sequence is an everyday task in several social science, computer science, engineering etc. projects. One approach is using Markov chains. The best available current result about the well-studied switch Markov chain is that it is rapidly mixing on P-stable degree sequences (see DOI:10.1016/j.ejc.2021.103421). The switch Markov chain does not change any degree sequence. However, there are cases where degree intervals are specified rather than a single degree sequence. (A natural scenario where this problem arises is in hypothesis testing on social networks that are only partially observed.) Rechner, Strowick, and Müller-Hannemann introduced in 2018 the notion of degree interval Markov chain which uses three (separately well-studied) local operations (switch, hinge-flip and toggle), and employing on degree sequence realizations where any two sequences under scrutiny have very small coordinate-wise distance. Recently Amanatidis and Kleer published a beautiful paper (arXiv:2110.09068), showing that the degree interval Markov chain is rapidly mixing if the sequences are coming from a system of very thin intervals which are centered not far from a regular degree sequence. In this paper we extend substantially their result, showing that the degree interval Markov chain is rapidly mixing if the intervals are centred at P-stable degree sequences.
