基于R语言igraph包的k正则图迭代加边：维持度数一致并保留连接

我来帮你搞定这个迭代扩展正则图的需求，核心思路是每次迭代生成一个和现有边完全不重复的完美匹配（1-正则图），然后把它和当前的图合并——这样既能保证所有节点的度数同步增加1，又能完整保留之前所有的连接关系，完全符合你的要求。

实现步骤与代码示例 #

1. 初始生成k正则图 #

首先我们用k.regular.game生成初始的正则图，注意节点数必须是偶数（你已经满足这个前提啦）：

library(igraph)

# 定义参数：偶数节点数、初始度数k
n_nodes <- 10
k_initial <- 2

# 生成初始k正则无向图
g_initial <- k.regular.game(n = n_nodes, k = k_initial, directed = FALSE)

2. 编写迭代扩展函数 #

我写了一个封装好的函数，它会帮你完成指定次数的迭代扩展，每次都保证度数统一增加，且不重复加边：

expand_regular_graph <- function(graph, iterations) {
  current_graph <- graph
  node_count <- vcount(current_graph)
  
  # 先检查最大可能迭代次数：节点最大度数是n-1，所以k_initial + iterations < node_count
  if (k_initial + iterations >= node_count) {
    stop(paste("迭代次数过多，最大允许迭代次数为", node_count - k_initial - 1))
  }
  
  for (i in 1:iterations) {
    # 先把现有边转换成排序后的字符串，方便后续查重
    existing_edges <- apply(get.edgelist(current_graph), 1, sort)
    existing_edge_strs <- paste(existing_edges[1, ], existing_edges[2, ], sep = "-")
    
    # 生成新的完美匹配，直到找到和现有边无重复的
    repeat {
      # 生成1-正则图（完美匹配）
      new_matching <- sample_degseq(rep(1, node_count), method = "vl")
      # 转换新边为字符串
      new_edges <- apply(get.edgelist(new_matching), 1, sort)
      new_edge_strs <- paste(new_edges[1, ], new_edges[2, ], sep = "-")
      
      # 检查是否有重复边，没有的话就跳出循环
      if (length(intersect(existing_edge_strs, new_edge_strs)) == 0) {
        break
      }
    }
    
    # 合并当前图和新的完美匹配
    current_graph <- union(current_graph, new_matching)
    
    # 可选：验证度数是否统一（调试用，实际可以删掉）
    stopifnot(all(degree(current_graph) == k_initial + i))
  }
  
  return(current_graph)
}

3. 调用函数并验证结果 #

比如我们迭代3次，最终每个节点的度数应该是2+3=5：

# 执行3次迭代扩展
g_expanded <- expand_regular_graph(g_initial, iterations = 3)

# 验证所有节点度数是否为5
all(degree(g_expanded) == 5)  # 应该返回TRUE

# 验证初始图的边是否全部保留在扩展后的图里
all(E(g_initial) %in% E(g_expanded))  # 应该返回TRUE

关键逻辑解释 #

• 完美匹配的作用：每次生成的完美匹配是1-正则图，每个节点恰好连一条新边，这样所有节点的度数会同步+1，天然满足“所有节点度数一致”的要求。
• 去重检查：生成新匹配后必须检查是否和现有边重复，否则会导致部分节点度数多增加，或者邻居集合没有真正扩展。
• 度数上限限制：每个节点的最大度数是节点数-1（连到其他所有节点），所以迭代次数不能超过节点数 - k_initial - 1，函数里已经加了这个检查避免报错。

内容的提问来源于stack exchange，提问作者shazz