R语言自定义k-core算法结果与igraph::coreness不符问题排查

问题重现 #

尝试在R中实现k-core算法，但自定义函数输出与igraph::coreness不符。自定义函数及测试代码如下：

自定义k-core函数 #

my_kcores <- function(W){
  deg    <- colSums(W)
  maxd   <- max(deg)
  kcores <- integer( length(deg) )
  W_copy <- W
  for ( d in 0:maxd ){
    while ( any( (deg > 0) & (deg <= d) ) ){
      W_copy[ deg <= d ,] <- W_copy[, deg <= d ] <- 0
      deg                 <- colSums(W_copy)
    }
    kcores[ deg > d ] <- d + 1
  }
  return(kcores)
}

测试代码 #

library(igraph)
W <- matrix(c(0,0,0,1,
              0,1,0,0,
              0,0,1,1,
              1,0,1,0),
            nrow = 4, byrow = TRUE)
g <- graph_from_adjacency_matrix(W, mode = "undirected", weighted = FALSE)
coreness(g)
# [1] 1 2 2 1

my_kcores(W)
# [1] 1 1 1 1

all.equal(coreness(g), my_kcores(W))
# [1] "Mean relative difference: 0.5"

问题原因分析 #

自定义函数的核心逻辑存在两处关键错误：

• kcores赋值逻辑错误：循环中每次将deg > d的节点设为d+1，但后续更大的d值会覆盖之前的赋值。比如当d=1时，符合条件的节点会被设为2，但当d=2时，若这些节点的deg不再大于2，就不会被更新，最终无法保留节点所属的最大k值。
• 节点移除的逻辑偏差：直接将deg <= d的节点对应行列置0，但未标记节点已被移除，导致后续循环可能重复处理，且无法准确追踪每个节点最终能保留的最大k值。

k-core的正确逻辑是：每个节点的coreness是它所属的最大k值——即该节点在k-core子图中（子图所有节点度至少为k），且不在(k+1)-core子图中。正确流程是从最低度开始迭代移除节点，记录每个节点被移除时的d值（即其coreness），剩余节点的coreness为最终的最大k值。

修正后的函数 #

my_kcores_fixed <- function(W) {
  n <- nrow(W)
  deg <- colSums(W)
  kcores <- deg  # 初始化为当前度
  removed <- logical(n)
  
  # 从最低度开始处理
  current_min <- min(deg[!removed])
  while (current_min < max(kcores[!removed])) {
    # 找到当前度<=current_min且未被移除的节点
    to_remove <- which(!removed & deg <= current_min)
    if (length(to_remove) == 0) break
    
    # 标记这些节点的coreness为current_min，并标记已移除
    kcores[to_remove] <- current_min
    removed[to_remove] <- TRUE
    
    # 更新剩余节点的度
    for (node in to_remove) {
      neighbors <- which(W[node, ] == 1 & !removed)
      deg[neighbors] <- deg[neighbors] - 1
    }
    
    # 更新当前最小度
    if (any(!removed)) {
      current_min <- min(deg[!removed])
    } else {
      break
    }
  }
  
  # 最后剩余的节点，其coreness为当前的最小度（即最大的k）
  kcores[!removed] <- current_min
  return(kcores)
}

测试验证 #

my_kcores_fixed(W)
# [1] 1 2 2 1
all.equal(coreness(g), my_kcores_fixed(W))
# [1] TRUE

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