介数中心性的时间复杂度？
如果给定图的最短路径前驱矩阵，计算介数中心性的时间复杂度是多少？
前驱矩阵单元如下所示：
- 如果节点i和节点j直接连接，则单元中的值为0；
- 如果节点i和节点j未连接，则单元格中的值为-1；
- else cell = 前驱(j) - 如果存在一条最短路径，则只能是一个前驱；如果 i 之间存在多个最短路径，则只能是一组前驱和j。
谢谢您的回答，
我熟悉布兰德斯算法。然而，布兰德斯算法将计算网络内所有节点的介数。我认为计算一个顶点的 CB 所花费的时间与计算所有顶点的 CB 所花费的时间相同，因为 Brandes 算法无法适应这种情况。
所以，我的想法是存储前驱矩阵，并能够计算某个顶点的 CB（而不必等待所有顶点的 CB 计算）。 我知道我无法实现更小的时间复杂度，但我认为时间量的差异可以通过不计算所有 7000 个顶点的 CB 来实现。相反，通过这个矩阵，我可以只计算一个顶点的 CB。
我认为可以在 O(n^2*L) 中计算 CB，其中 L 是当我们有前驱矩阵时的平均最短路径。
您对这个概念有何看法？
What is the time complexity of computing betweenness centrality if we are given the shortest path predecessor matrix of a graph?
Predecessor matrix cells look like this:
- if node i and node j are directly connected then value in the cell is 0;
- if node i and node j are not connected then value in the cell is -1;
- else cell = predecessor(j) - this can be only one predecessor if there is a single shortest path or an array of predecessors if there are more than one shortest paths between i and j.
Thank you for your answer,
I am familiar with Brandes Algorithm. However Brandes Algorithm will compute the betweenness for all the nodes inside a network. I think that time spent for computing CB for one vertex is the same as the time for computing CB for all vertices as Brandes algorithm can't be adapted for such a case.
So, my idea was to store the predecessor matrix, and to be able to compute CB for a certain vertex (and not have to wait for all vertices CB computations).
I am aware I can't achieve smaller time complexity but I think that the difference in amount of time can be made by not computing CB for all 7000 vertices. Instead, by having this matrix I am able to compute CB for only one single vertex.
I think it is possible to compute CB in O(n^2*L) where L is the average shortest path when we have predecessor matrix.
What is your opinion about this concept?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
据我所知，最著名的计算介数中心性的算法是本文中描述的算法：
您将看到，作为第一步，该算法计算每对节点之间的最短路径的数量。这样做的方式很自然，同时也计算前驱矩阵。因此，预先计算前驱矩阵似乎没有任何好处：在执行布兰德斯算法时，您基本上可以免费获得它。
（当然，这并不能证明它没有区别，也许其他人更了解。您可能想在 cstheory.stackexchange 上询问。 com。）
As far as I can find out, the best known algorithm for computing betweenness centrality is the one described in this paper:
You'll see that this algorithm computes, as a first step, the number of shortest paths between every pair of nodes. It is natural to do so in a way that simultaneously computes the predecessor matrix too. So it appears that there's no benefit to pre-computing the predecessor matrix: you get it essentially for free anyway while executing Brandes' algorithm.
(Of course, this isn't a proof that it makes no difference, and maybe someone else knows better. You might want to ask on cstheory.stackexchange.com.)