brandes_betweenness_centrality doesn't give correct result when network is large

[heshan@…]

I'm using the C++ version. My network is a 2D regular lattice. when number of nodes in the network is small, N<35*35，the betweenness returned by brandes_betweenness_centrality() is correct, but when N>35*35，the result is wrong. when N=50*50，the betweenness is at the magnitude of order 1e9, which is obviously wrong. I also use betweenness function provided by JUNG to confirm that this is a bug. But java is too slow, I decide to implement brandes algorithm on my own. To my surprise, my program has the exactly same problem as the brandes_betweenness_centrality(). This seems to be an overflow problem. I find that the variable to record the number of path between source and every other vertex should have large enough representation range. I previously use unsigned int. After I change the type to double, the problem is fixed. the simplest code to reproduce the bug are in the following:

#include <iostream> #include <vector> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/betweenness_centrality.hpp> using namespace std; using namespace boost;

int main() {

typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, double> > graph_t; const unsigned int L = 50; const unsigned int vertexnum = L * L; graph_t graph(vertexnum); unsigned int upper, left;

for( unsigned int vertexidx = 0; vertexidx < vertexnum; ++vertexidx ) {

upper = ( vertexidx < L ) ? ( L * ( L - 1 ) + vertexidx ) : ( vertexidx - L ); left = ( vertexidx % L ) ? ( vertexidx - 1 ) : ( vertexidx + L - 1 ); add_edge( vertex( vertexidx, graph ), vertex( upper, graph ), graph ); add_edge( vertex( vertexidx, graph ), vertex( left, graph ), graph );

}

vector<double> betweenness( num_vertices( graph ) ); brandes_betweenness_centrality( graph, centrality_map( make_iterator_property_map(

betweenness.begin(), get( vertex_index, graph ) ) )

); copy( betweenness.begin(), betweenness.end(), ostream_iterator<double>( cout, " " ) ); return EXIT_SUCCESS;

}

[Douglas Gregor]

(In [40645]) Use unsigned long long for the path count to avoid overflows. Fixes #1398