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

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 – Maria Ines Parnisari Nov 5 '14 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. – orezvani Nov 5 '14 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 – Maria Ines Parnisari Nov 6 '14 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 – Maria Ines Parnisari Nov 6 '14 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. – orezvani Nov 6 '14 at 4:56