时间戳

首页 > 解决方案 > R igraph 包如何计算接近中心性？

r - R igraph 包如何计算接近中心性？

问题描述

我有以下网络：

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")

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

标签： rigraph

解决方案

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

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

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

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

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

接近度由 Bavelas (1950) 定义为距离的倒数，即：
C(x) = 1 / ∑ d(y,x)

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

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

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

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

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

您不应该忽略这些节点。您应该将距离设置为图中的节点总数。因此，要获得与 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). 如 Wikipedia 中所述，对于大型图表，它们本质上是相同的，但我只是想确保您知道您正在计算什么。

推荐阅读