如何在R中实现无向连通图上的Metropolis-Hastings算法？

核心转移概率推导 #

目标是模拟顶点集上的均匀分布，提议分布采用图上的随机游走：

• 若当前处于顶点x，提议转移到任意邻居y的概率为1/d(x)，其中d(x)是x的度数
• Metropolis接受概率：由于目标分布是均匀分布，π(x)=π(y)=1/5，因此接受概率α(x→y) = min(1, d(x)/d(y))
• 最终转移概率：
  • 对x的邻居y：P(x→y) = (1/d(x)) * min(1, d(x)/d(y))
  • 停留概率：P(x→x) = 1 - 所有邻居转移概率之和

R代码实现 #

步骤1：模拟局部信息获取（模拟未知图结构的局部查询） #

我们先定义一个5顶点的无向连通图，并实现两个局部查询函数，实际场景中只需替换查询逻辑即可：

• 获取当前顶点的邻居列表
• 获取任意顶点的度数

# 定义示例5顶点无向图的邻接表（键是顶点，值是邻居列表）
graph_adj <- list(
  1 = c(2, 3),
  2 = c(1, 4, 5),
  3 = c(1, 4),
  4 = c(2, 3),
  5 = c(2)
)

# 获取顶点x的邻居列表
get_neighbors <- function(x) {
  return(graph_adj[[as.character(x)]])
}

# 获取顶点x的度数
get_degree <- function(x) {
  return(length(get_neighbors(x)))
}

步骤2：实现Metropolis-Hastings采样算法 #

metropolis_hastings_graph <- function(n_samples, start_vertex) {
  # 初始化结果存储
  samples <- numeric(n_samples)
  samples[1] <- start_vertex
  current_x <- start_vertex
  
  for (i in 2:n_samples) {
    # 从当前顶点的邻居中随机选一个提议状态y（随机游走提议）
    neighbors_x <- get_neighbors(current_x)
    proposal_y <- sample(neighbors_x, size = 1)
    
    # 计算接受概率
    d_x <- get_degree(current_x)
    d_y <- get_degree(proposal_y)
    acceptance_prob <- min(1, d_x / d_y)
    
    # 决定是否接受提议
    u <- runif(1)
    if (u <= acceptance_prob) {
      current_x <- proposal_y
    }
    
    # 记录当前状态
    samples[i] <- current_x
  }
  
  return(samples)
}

# 运行采样：生成10000个样本，从顶点1开始
samples <- metropolis_hastings_graph(n_samples = 10000, start_vertex = 1)

# 查看采样结果的频率分布（验证是否接近均匀分布）
table(samples) / length(samples)

代码说明 #

• 模拟未知图结构：get_neighbors和get_degree函数模拟了“仅能获取局部信息”的场景——不需要知道整个图的结构，只需能查询当前顶点的邻居和任意顶点的度数即可
• 采样逻辑严格遵循Metropolis-Hastings规则：随机游走提议、计算接受概率、随机判断是否接受
• 最终的频率分布会趋近于均匀分布（每个顶点的概率接近0.2）

内容的提问来源于stack exchange，提问作者Homer Jay Simpson