iGraph - k-core 的 graph.coreness 低估了一些核心

Question

我正在 R 中使用 iGraph 来计算一组 10 个节点的 k 核。其中 8 个节点相连，且度数为 5 或更大，另外两个节点的度数仅为 3。

根据我对 k 核的理解，所有连接且度数至少为 5 的 8 个节点不应该都在值为 5 的 k 核中吗？然而，这 8 个中的两个的 k 核心值分别为 4 和 3。

请参阅下面的可重现图表：

el = matrix(c("Ns-1","Ns-1","Ns-1","Ns-1","Ns-1","Ns-1","Ns-1","Ns-1","Ns-14","Ns-14","Ns-15","Ns-15","Ns-15","Ns-17","Ns-17","Ns-17","Ns-17","Ns-2","Ns-2","Ns-2","Ns-2","Ns-4","Ns-4","Ns-4","Ns-5","Ns-5","Ns-5","TAMU-7","Ns-14","Ns-15","Ns-17","Ns-2","Ns-4","Ns-5","TAMU-7","TAMU-8","Ns-15","Ns-17","Ns-17","Ns-4","Ns-18","Ns-2","Ns-4","Ns-5","Ns-18","Ns-4","Ns-5","TAMU-7","TAMU-8","Ns-5","TAMU-7","TAMU-8","TAMU-7","TAMU-8","Ns-18","TAMU-8"),nrow=28,ncol=2)

graph = graph.edgelist(el[,1:2],directed=F)

l <- layout.kamada.kawai(graph)
V(graph)$x <- l[,1]
V(graph)$y <- l[,2]

V(graph)$kCore = graph.coreness(graph)
V(graph)$degree = degree(graph)

layout(matrix(c(1,2), 1, 2))
plot(graph,
 main="Degree",
 vertex.size = 20,
 vertex.label = V(graph)$degree,
 vertex.label.color = "black",
 vertex.label.font = 1,
 vertex.label.family = "sans",
 vertex.label.cex = 1,
 vertex.color = "white")

plot(graph,
 main="K Cores",
 vertex.size = 20,
 vertex.label = V(graph)$kCore,
 vertex.label.color = "black",
 vertex.label.font = 1,
 vertex.label.family = "sans",
 vertex.label.cex = 1,
 vertex.color = "white")

...它生成同一图的图像（https://www.dropbox.com/s/unkkgodf8ppteyq/igraph.png?dl=0），度数显示在左侧，k-core 显示在右侧。

基本上，左上角和右上角的节点的度数和 k 核数应均为 3。其余节点应为 5，但顶部中间的两个节点不是。

这是 iGraph 中的错误，还是我对 k-core/graph.coreness算法的理解错误？

Answer 1

根据我对 k 核的理解，所有连接且度数至少为 5 的 8 个节点不应该都在值为 5 的 k 核中吗？然而，这 8 个中的两个的 k 核心值分别为 4 和 3。

不。 k-core 是图的一部分，如果您迭代地删除所有度数小于k的节点，这意味着如果某些节点的度数由于删除其他节点而低于k，则必须也删除这些节点。剩余的 k 核是一个子图，其中所有节点的度数至少为k。在您的特定情况下，删除图形最左侧的节点并删除最上面的节点（位于右上角）会降低其他两个节点的度数低于 5 - 因此它们也会被删除。