2

我正在创建一个程序，它将计算未加权图中所有节点的 Betwenness Centrality。为此，我必须找到 ASSSP（所有单源最短路径）。在创建程序时，我开始意识到最终我会建立联系（从源到目的地的距离相同，但路径不同）。这让我想到了这个问题。我应该如何解决这些关系？如果我使用随机分线器，那么对于相同的输入，中介中心性的每个输出可能会略有不同。让我做一个小的示例图：

   A
  / \
B    C
  \ /
   D

现在假设 A 节点是我们希望找到 ASSSP 的源。可以清楚地看到存在两条路径（A->B->D 和 A->C->D），它们的 bot 长度相同，都是最短的。现在我应该选择哪一个，在什么条件下？

随机决胜局（问题）

如果我使用随机的决胜局，就像找到的第一个一样，被标记为最短路径（程序是分布式的，所以这个解决方案将以随机方式工作）。然后我会遇到中间中心性问题，因为节点 B 和 C 的值会有所不同；取决于哪个路径被标记为最短。

有谁知道如何解决这个问题，或者我只是错过了什么？

4

3 回答 3

1

要正确计算介数中心性，您必须考虑图中的每条最短路径。如果两个节点 A 和 B 之间有k条最短路径，则每条最短路径将对路径通过的节点的总介数分数贡献1/k 。通常，您不应该通过实际查找（并存储）网络中的所有最短路径来计算中间中心性；有关更有效的算法，请参阅以下论文：

一种更快的中介中心性算法

于 2012-07-11T18:20:51.273 回答
0

很大程度上由于您注意到的问题，介数中心性实际上不是通过仅检查源和目标之间的单个路径来计算的，而是通过计算最短路径的数量来计算的。您需要为此修改合适的最短路径算法，例如 Floyd–Warshall 算法或 Johnson 算法。

于 2012-07-11T17:47:49.523 回答
0

是的，SSSP 或单源最短路径是计算机科学中非常常见的问题。一个标准做法是，您遇到的第一条路径比其他相同距离的路径短。

例如，在您的示例中，如果在您之前处理A->B->D过的算法中A->C->D，那么A->B->D将是最短路径。

如果事情仍然不清楚，我相信 Dijkstra 的算法就是你所追求的。

于 2012-07-11T16:08:11.473 回答