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:
1--2--3
i would expect BC of 1/3 for node2
, but this algorithm gives me2
$\endgroup$ – Maria Ines Parnisari Nov 6 '14 at 0:31