计算的时间复杂度是多少betweenness centrality如果给定一个图的最短路径前驱矩阵？
前驱矩阵单元格如下所示:
- 如果节点i和节点j直接相连，则单元格中的值为0；
- 如果节点 i 和节点 j 没有连接，则单元格中的值为 -1；
- else cell = predecessor(j) - 如果只有一条最短路径，则这只能是一个前驱；如果 i< 之间有多个最短路径，则这可以是一个前驱数组/em> 和 j。
谢谢你的回答，
我熟悉 Brandes 算法。然而，Brandes 算法将计算网络内所有节点的介数。我认为计算一个顶点的 CB 所花费的时间与计算所有顶点的 CB 所花费的时间相同，因为 Brandes 算法无法适应这种情况。
所以，我的想法是存储前导矩阵，并能够为某个顶点计算 CB(而不必等待所有顶点的 CB 计算)。 我知道我无法实现更小的时间复杂度，但我认为可以通过不计算所有 7000 个顶点的 CB 来实现时间量的差异。相反，通过使用这个矩阵，我可以只为一个顶点计算 CB。
我认为在 O(n^2*L) 中计算 CB 是可能的，其中 L 是我们有前置矩阵时的平均最短路径。
你对这个概念有什么看法？
最佳答案
据我所知，最著名的计算介数中心性的算法是本文中描述的算法:
- 乌尔里克·布兰德斯 (2001)。 A Faster Algorithm for Betweenness Centrality .数学社会学杂志 25(2):163-177.
您将看到，作为第一步，该算法会计算每对节点之间的最短路径数。以同时计算前驱矩阵的方式这样做是很自然的。因此，预先计算前驱矩阵似乎没有任何好处:在执行 Brandes 算法时，您基本上可以免费获得它。
(当然，这并不能证明它没有任何区别，也许其他人知道得更多。您可能想在 cstheory.stackexchange.com 上提问。)
关于algorithm - 中介中心性的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6532349/