R igraph 包如何计算 Closeness Centrality？

Question

我有以下网络：

g <- graph(c("Amy", "Ram",
          "Ram", "Li",
          "Li", "Amy",
          "Amy", "Li",
          "Kate", "Li"), directed=TRUE)

并想了解如何计算该网络中的接近度中心性。根据我对文档的理解，接近度是从一个顶点到网络的每个其他顶点的所有最短路径的平均值的倒数。直觉上，我会这样计算它：

Dist <- distances(g, mode="out")
Dist[Dist == Inf] <- NA
1/rowMeans(Dist, na.rm=T)

然而，这很可能是不正确的，因为用于计算接近度中心性的内置 igraph 函数的值显示了不同的结果：

closeness(g, mode = "out")

我想了解如何计算接近度以及如何在不使用内置函数的情况下逐步获得相同的结果。

Answer 1

这里发生了几件事。你的代码中确实有一个错误，但最大的问题是函数closeness——无论是它的实现还是它的文档。首先，我们应该计算什么？igraph 文档closeness说：

\n\n

\n

顶点的接近中心性由图中到/自所有其他顶点的最短路径平均长度的倒数定义：

\n\n

1/sum( d(v,i), i != v)

\n\n

如果顶点 v 和 i 之间没有（有向）路径，则公式中将使用顶点总数而不是路径长度。

\n

\n\n

让我们将其与维基百科关于 closeness_centrality 的文章中的内容进行比较。

\n\n

\n

Bavelas (1950) 将接近度定义为\n 距离的倒数，即：
\n C(x) = 1 / \xe2\x88\x91 d(y,x)

\n\n

其中 d(y,x) 是顶点 \nx 和 y 之间的距离。当谈到接近中心性时，人们通常指的是其标准化形式，它表示最短路径的平均长度，而不是它们的总和。一般由前面的公式乘以 N \xe2\x88\x92 1 给出，其中 N 是图中的节点数。对于大图，这种差异\n变得无关紧要，因此 \xe2\x88\x921 被删除\n，导致：
\n C(x) = N / \xe2\x88\x91 d(y,x)

\n\n

此调整允许在不同大小的图形节点之间进行比较。

\n

\n\n

首先，igraph 文档将总和超过i != v。
\n这些词表示“平均长度的倒数”，这意味着 \nC(x) = (N-1) / \xe2\x88\x91 d(y,x) 但公式表示1 / \xe2\x88\x91 d(y,x)。事实上，我们将看到closeness函数计算的内容与原始定义相对应，尽管单词表示标准化版本。

\n\n

但还有另外一个问题。您将 Inf 值更改为 NA，然后使用na.rm=T。请注意 igraph 文档中的最后一句。

\n\n

\n

如果顶点 v 和 i 之间没有（有向）路径，则公式中将使用顶点总数 \n 而不是路径长度。

\n

\n\n

您不应该忽略这些节点。您应该设置与图中节点总数的距离。因此，要获得与 igraph 生成的结果相同的结果，您需要计算：

\n\n

Dist <- distances(g, mode="out")\nDist[Dist == Inf] <- vcount(g)\n1/rowSums(Dist)\n      Amy       Ram        Li      Kate \n0.1666667 0.1428571 0.1428571 0.1666667 \ncloseness(g, mode = "out")\n      Amy       Ram        Li      Kate \n0.1666667 0.1428571 0.1428571 0.1666667 \n

\n\n

当然，igraph 文档不一致。文字上说它计算归一化的接近度，但公式（以及它实际计算的内容）是非归一化的形式。

\n\n

我希望这能让您清楚计算什么，并帮助您选择要用于分析的内容。

\n\n

顺便说一句：当您计算 时1/rowMeans(Dist)，您包括了 igraph 遗漏的 v=i 情况（其中距离为零）。这意味着您正在计算C(x) = N / \xe2\x88\x91 d(y,x)而不是C(x) = (N-1) / \xe2\x88\x91 d(y,x)。正如维基百科所述，对于大型图，它们本质上是相同的，但我只是想确保您知道您正在计算的内容。

\n