What is the rationale behind division by 2 for the undirected Brandes
calcuation?
Also, can someone show me how to get the weighted version of brandes?
The following code calculates the unweighted version.
#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/graph_utility.hpp"
#include "boost/graph/betweenness_centrality.hpp"
using namespace boost;
int main(int argc, char * argv[]){
const int N = 6;
typedef property < edge_weight_t, double > WeightMap;
typedef property < vertex_centrality_t, double > CentralityMap;
typedef adjacency_list UndirectedGraph;
UndirectedGraph g(N);
add_edge(0, 1, 3, g);
add_edge(0, 2, 2, g);
add_edge(0, 3, 6, g);
add_edge(0, 4, 4, g);
add_edge(1, 3, 5, g);
add_edge(1, 5, 5, g);
add_edge(2, 4, 1, g);
add_edge(3, 4, 2, g);
add_edge(3, 5, 1, g);
add_edge(4, 5, 4, g);
print_graph(g);
brandes_betweenness_centrality(g,
get(vertex_centrality,g),
get(edge_weight, g)
);
boost::property_map::type
b = get(vertex_centrality, g);
graph_traits < UndirectedGraph >::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
printf("BRANDES centr[%d] = %g\n",
*vi,
b[*vi]);
}
}
Boost/graph gives the following:
0 <--> 1 2 3 4
1 <--> 0 3 5
2 <--> 0 4
3 <--> 0 1 4 5
4 <--> 0 2 3 5
5 <--> 1 3 4
I AM HERE dispatch2
CALLING UNWEIGHTED
BRANDES centr[0] = 1.83333
BRANDES centr[1] = 0.333333
BRANDES centr[2] = 0
BRANDES centr[3] = 0.666667
BRANDES centr[4] = 1.83333
BRANDES centr[5] = 0.333333
While networkx gives:
http://networkx.lanl.gov/reference/generated/networkx.betweenness_centrality...
{0: 3.6666666666666665, 1: 0.66666666666666663, 2: 0.0, 3:
1.3333333333333333, 4: 3.6666666666666661, 5: 0.66666666666666663}
So, boost is exactly 1/2 of networkx's solution.
Is one version wrong? Or is this some kind of convention that boost and
networkx disagree on?
Thanks,
Matt
