Fast and perfect sampling of subgraphs and polymer systems
Fast and perfect sampling of subgraphs and polymer systems
复制标题
DOI：
10.1145/3632294
复制
发表时间：
2022-02
影响因子：
1.3
通讯作者：
Antonio Blanca;Sarah Cannon;Will Perkins
中科院分区：
文献类型：
--
作者：
Antonio Blanca;Sarah Cannon;Will Perkins
本文给出了有根有界度图的加权连通诱导子图（或小图）的一个有效的完美抽样算法。我们的算法采用了一个顶点渗滤过程与精心选择的拒绝过滤器和渗滤亚临界条件下的工程。我们表明，这个条件是最佳的意义上说，（近似）采样加权根graphlets的任务变得不可能在有限的预期时间为无限的图形和棘手的有限图形时，条件不成立。我们应用我们的采样算法作为一个子程序，给近线性时间完美的采样算法的聚合物模型和加权非根graphlets在有限图，两个广泛研究，但非常不同的问题。这种新的完美的聚合物模型的采样算法，在其他应用中，在低温下的膨胀图和不平衡二分图的自旋系统提供了改进的采样算法。
We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.