r - 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 核。

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

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

Answer 1

From my understanding of k cores, shouldn't the 8 nodes that are all connected, and that have a degree of at least 5 all be in a k-core with value 5? Two of these 8, are being given k-core value of 4 and 3 however.

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