是否有一种有效的算法来均匀采样包含给定节点的给定大小的所有连通子图

Question

我有一个未加权的 d-正则图，我希望对包含给定节点的给定大小的所有连接子图进行统一采样。 是否有已知的算法可以做到这一点？

Answer 1

是的，有一种有效的方法可以对固定大小的连通子图进行均匀采样 𝑘 包含给定节点涉及使用马尔可夫链蒙特卡罗 (MCMC) 技术。您可以使用MCMC进行统一采样 您可以从大小的初始子图结构开始 𝑘 包含给定节点 𝑣 0，一个简单的方法是从以下位置开始执行 BFS 或 DFS 𝑣 0 并添加节点直到子图有 𝑘 节点。

连接性：在转换过程中保持子图的连接性至关重要。这可以通过 BFS/DFS 进行检查 𝑂 （ 𝑘 ） 时间，因为子图大小是 𝑘。 对于 𝑑 来说效率是正常的 对于常规图，这种方法的计算效率很高，因为检查转换的邻居数量是有限的。