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

Improve this question
$\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$
    – Maria Ines Parnisari
    Nov 5 '14 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 '14 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$
    – Maria Ines Parnisari
    Nov 6 '14 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$
    – Maria Ines Parnisari
    Nov 6 '14 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 '14 at 4:56
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You're absolutely right. It turned out to be an error in my implementation. Thanks! $\endgroup$
    – Maria Ines Parnisari
    Nov 8 '14 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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