Time complexity of betweenness centrality?

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?

As far as I can find out, the best known algorithm for computing betweenness centrality is the one described in this paper:

• Ulrik Brandes (2001). A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177.

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