# Betweenness centrality measurement ignoring inverse paths?

I'm implementing the Betweenness Centrality algorithm proposed by Brandes (first algorithm on this paper - also below), and I'm running into a very weird issue: it seems to be ignoring some paths (i.e. for vertexes v-w, it may count the path v-e-w, but not the inverted path w-e-v). I'm not sure how to prove or debug this issue, but I'm pretty certain that's what happening. The precise issue that I can see in the debugger is that two nodes that should have the same BC value are off by roughly three units. I'm using the double type to store the values.

Am I missing something about this algorithm? The graph I'm examining is unweighted and undirected btw.

Also, on a totally unrelated note: the value being computed on each step is the following:

Shouldn't the value be between 0 and 1?

Algorithm:

• I think it's a bug in the pseudocode. I've translated it to c# and i'm getting BC values greater than 1 Commented Nov 5, 2014 at 13:48
• Be realistic man, there is no bug in this psuedocode. Brendas's algorithm is used by everyone including many famous libraries. Try to find the bug in your code and see which part you haven't understood. Commented Nov 5, 2014 at 23:42
• Do you have any links to implementations? The second line starting from the end is giving me values > 1 all the time Commented Nov 6, 2014 at 0:17
• Let me give you an example. On graph 1--2--3 i would expect BC of 1/3 for node 2, but this algorithm gives me 2 Commented Nov 6, 2014 at 0:31
• I deleted my first comment. The value can be larger than 1. In the example that you mentioned, node 2 has BC 2 and the output is correct. Commented Nov 6, 2014 at 4:56

## 1 Answer

The algorithm that you have mentioned here is definitely correct. You can refer to the correctness proof in the paper.

This algorithm is implemented in many libraries and ready to be used including NetworkX, Boost, GraphStream, and MATLAB (3rd party I guess) and many others. Also, many other people (including myself) and companies have employed the same algorithm.

If you are getting unexpected results, please revise your implementation.

• You're absolutely right. It turned out to be an error in my implementation. Thanks! Commented Nov 8, 2014 at 0:10