0
$\begingroup$

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: enter image description here

Shouldn't the value be between 0 and 1?

Algorithm:

enter image description here

$\endgroup$
6
  • $\begingroup$ I think it's a bug in the pseudocode. I've translated it to c# and i'm getting BC values greater than 1 $\endgroup$ Nov 5, 2014 at 13:48
  • $\begingroup$ 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. $\endgroup$
    – orezvani
    Nov 5, 2014 at 23:42
  • $\begingroup$ Do you have any links to implementations? The second line starting from the end is giving me values > 1 all the time $\endgroup$ Nov 6, 2014 at 0:17
  • $\begingroup$ 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 $\endgroup$ Nov 6, 2014 at 0:31
  • $\begingroup$ 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. $\endgroup$
    – orezvani
    Nov 6, 2014 at 4:56

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.