论文标题
快速而完美的子图和聚合物系统的采样
Fast and perfect sampling of subgraphs and polymer systems
论文作者
论文摘要
我们提供了有效的完美采样算法，用于植根的，有界度图的加权，连接的诱导子图（或图形）。我们的算法利用了带有精心选择的拒绝过滤器的顶点渗透过程，并在渗透率下临界条件下工作。我们表明，这种条件是最佳的，因为在无限图的有限预期时间中，（大约）采样加权的扎根图的任务是不可能的，而在条件不运行时对于有限图很难。我们将采样算法应用于子例程，以在有限图中为聚合物模型和加权的非根系图提供接近线性的完美采样算法，两个研究了两个问题，但问题却非常不同。这种针对聚合物模型的新的完美采样算法可改善在扩展器图和不平衡的两部分图上的低温下自旋系统的采样算法，以及其他应用。
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.
