R 中从头开始的 k 核心

Question

我尝试在R中实现k-core算法。但是结果与

igraph::coreness

中的结果不同。

根据我对 R 中该算法的理解，我创建的函数是这样的：

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"

Answer 1

我不认为你的算法有问题，但你应该意识到

W

中的对角线条目，这表明自循环，比如说，你有向内/向外的弧同时指向自身。

您应该进行

W

的预处理，然后运行

my_kcores

，例如，

> (WW <- `diag<-`(W, 2 * diag(W)))
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    1
[2,]    0    2    0    0
[3,]    0    0    2    1
[4,]    1    0    1    0

> my_kcores(WW)
[1] 1 2 2 1