Betweenness centrality Brandes algorithm

Question

I was reading about Betweenness Centrality based on Brandes algorithm. I have some questions regarding the algorithm

1. Whether this algorithm gives exact betweenness centrality or an approximation? When I run BC on Sage, which is based on Brandes algorithm, it didnt gave exact value. For example instead of 14, I got 13.9956......

2. Could someone explain "Accumulation of Pair-Dependencies" section on more simpler terms?

3. What to be done when for "We need to store a dependency per vertex, and lists of predecessors." Whether this is done when Dijkstra algorithm is executed?

4. What to be done for weighted graphs?

Answer 1

1. The Brandes' algorithm gives the exact centrality of each vertex. I don't know which implementation of the algorithm is used in Sage, but chances are that it's a precision problem.

2. The accumulation part of the algorithm is probably the trickiest. When you reach that part, you have in sigma the amount of shortest paths from the current vertex s to the rest of the vertices. Also, in Pred, you have for each vertex, the list of vertices that reach them through a shortest path. The dependency delta will be the amount of betweenness that s will contribute to the rest of vertices (ranging from 0 to N-2), i.e., how much depends s on each vertex.

   A vertex w is popped from S until empty, starting with the furthest one from s and ending with s itself (keep in mind that a vertex was added to S when it was reached in the shortest path count part of the algorithm). For each v in the list of predecessors of w (Pred[w]), a new value for the dependency is calculated, and that's (for me) the tricky part.

   The expression says delta[v] = delta[v] + (sigma[v]/sigma[w]) * (1 + delta[w]), or, to put it in other words, the new dependency for v is the dependency that it already had plus (sigma[v]/sigma[w]) * (1 + delta[w]). Well, first of all, note that when a vertex w is popped from S, its whole dependency delta[w] has been calculated, because there will be no future nodes further than w, so it cannot be in the middle of any other shortest path. Then, it should be clear that (sigma[v]/sigma[w]) is the dependency of the pair (s, w) of v, that is, how much depend the vertices s and w of v to remain connected (because it is the proportion of shortest paths from s to w passing through v). But (and this is the less obvious part, I think), the vertex v is not only in the shortest paths between s and w, it's also in all the shortest paths in which w was involved! So, if there was a shortest path from s to some vertex x passing through w, then there must be a path from s to x passing through v. To put it simple, s will depend more on v if it depended a lot on w. So, the factor (1 + delta[w]) is explained as follows: 1, for the dependency of v of the pair (s, w), and delta[w] for the dependency of v of every pair (s, <any vertex beyond w>).

   Finally, delta[w] is added to its full betweenness Cb[w] (unless w == s, because s is not considered of be dependent of itself).

   As I said, it's not an easy algorithm to understand at first glance. Take your time and please comment if you still have doubts.

3. I'm not completely sure what you're referring here. If you are asking how can you get the list of predecessors from the output of the Dijkstra algorithm, well, you cannot, at least directly. If you want to implement this algorithm using a pre-existing Dijkstra algorithm, you will not be able unless the algorithm allows for some kind of visitor during its execution, like the Boost Graph library Dijkstra implementation. Btw, this library already implements this algorithm (see here), and even a distributed/parallel version (here and here), if you're interested on that.

4. There are (at least) two ways you can consider weights in the betweenness calculation (I'm assuming you mean edge weights): as "length", so it has an influence on the shortest paths calculation, and as "importance" or "multiplicity" (e.g. the number of times a relationship appears). Brandes himself provides several variants for these and other cases on his paper On Variants of Shortest-Path Betweenness Centrality and their Generic Computation, algorithms 10 (for "length") and 11 (for "multiplicity"). Note that there is an error in the algorithm 11 of this paper, which is explained in Brandes' publications page (look for the name of the paper in the list).