r - 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功能 - 无论是它的实现还是它的文档。首先，我们应该计算什么？ closeness 的 igraph 文档说:

The closeness centrality of a vertex is defined by the inverse of the average length of the shortest paths to/from all the other vertices in the graph:

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

If there is no (directed) path between vertex v and i then the total number of vertices is used in the formula instead of the path length.

让我们将它与它在
Wikipedia article on closeness_centrality .

Closeness was defined by Bavelas (1950) as the reciprocal of the farness, that is:
C(x) = 1 / ∑ d(y,x)

where d(y,x) is the distance between vertices x and y. When speaking of closeness centrality, people usually refer to its normalized form which represents the average length of the shortest paths instead of their sum. It is generally given by the previous formula multiplied by N − 1 , where N is the number of nodes in the graph. For large graphs this difference becomes inconsequential so the −1 is dropped resulting in:
C(x) = N / ∑ d(y,x)

This adjustment allows comparisons between nodes of graphs of different sizes.

首先，igraph 文档将总和超过 i != v .
单词说“平均长度的倒数”，这意味着 C(x) = (N-1) / ∑ d(y,x)但公式说 1 / ∑ d(y,x) .
事实上，我们会看到 closeness函数计算对应
尽管有表示规范化版本的词，但仍遵循此原始定义。

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

If there is no (directed) path between vertex v and i then the total number of vertices is used in the formula instead of the path length.

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

Dist <- distances(g, mode="out")
Dist[Dist == Inf] <- vcount(g)
1/rowSums(Dist)
      Amy       Ram        Li      Kate 
0.1666667 0.1428571 0.1428571 0.1666667 
closeness(g, mode = "out")
      Amy       Ram        Li      Kate 
0.1666667 0.1428571 0.1428571 0.1666667 

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

我希望这可以清楚地说明正在计算的内容，并帮助您选择要用于分析的内容。

顺便说一句:当你计算 1/rowMeans(Dist) ，您包括 igraph 遗漏的 v=i 情况(距离为零)。这意味着您正在计算 C(x) = N / ∑ d(y,x)而不是 C(x) = (N-1) / ∑ d(y,x) .正如维基百科中所指出的，对于大图，它们本质上是相同的，但我只是想确保您知道您在计算什么。