1

我一直在回顾这篇有趣的文章：

http://kieranhealy.org/blog/archives/2013/06/09/using-metadata-to-find-paul-revere/

作为练习，我一直在挑选各种步骤来判定里维尔先生犯有叛国罪。有一次，作者使用了igraph 库的介数函数，描述为：

“顶点和边的介数（大致）由穿过顶点或边的测地线（最短路径）的数量定义。”

那么，在这篇文章的例子中，有多少人之间的最短通信路径要通过所考虑的 254 人中的每一个？不过，我从这篇文章中转移了一点注意力，我想知道我是否在天真地思考。

一个 254 x 254 的矩阵有 64516 个元素。然而，琐碎的元素（对角线上的那些——一个自言自语的人显然是从 X 到 X 的最短路径）可以打折，留下（似乎）254 * 254 - 254 = 64262 个非平凡有序配对。但是，这些不是定向的——也就是说，特定对 X 和 Y 之间的最短路径是相同的，无论 X 或 Y 中的哪一个是发送者，哪一个是接收者。

所以，我们可以减少配对的数量： (254 * 254 - 254) / 2 = 32131.

既然这也恰好是从 254 中选出的 2 的组合数，那就更好了——真是巧合！;-)

然后，只是为了好玩，我做了：

((254 * 254 - 254) / 2) - sum(betweenness(person.g)) = 10061

这个数字是什么意思？几乎似乎说有 10,061 对没有路径存在，但我不明白这怎么可能。我误解了中间性吗？提前谢谢了。

4

1 回答 1

1

如果您检查更简单的图形上发生的情况，您会注意到长度为 1 的最短路径不会进入计算。

betweenness( graph.lattice( 3 ) )
# [1] 0 1 0

长度为 2 的最短路径将被使用一次（用于中间的点），但长度为 3 或更长的最短路径将被使用多次：中间的每个点一次。

betweenness( graph.lattice( 5 ) )
# [1] 0 3 4 3 0

在这个例子中，最短路径是

length 1: 1-2, 2-3, 3-4, 4-5  (not used)
length 2: 1-3, 2-4, 3-5       (each used once, for the betweenness of 2, 3 and 4)
length 3: 1-4, 2-5            (each used twice, for 2,3 and 2,4)
length 4: 1-5                 (each used 3 times, for 2, 3 and 4)

换句话说，长度为 k 的最短路径被计算 k-1 次。

p <- shortest.paths(person.g)
sum( p[upper.tri(p)] - 1 )
# [1] 22070
sum( betweenness( person.g ) )
# [1] 22070
于 2013-08-22T17:49:12.280 回答