https://svn.boost.org/trac10/ticket/1398 <p> I'm using the C++ version. My network is a 2D regular lattice. when number of nodes in the network is small, N&lt;35*35，the betweenness returned by brandes_betweenness_centrality() is correct, but when N&gt;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: </p> <p> #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;boost/graph/graph_traits.hpp&gt; #include &lt;boost/graph/adjacency_list.hpp&gt; #include &lt;boost/graph/betweenness_centrality.hpp&gt; using namespace std; using namespace boost; </p> <p> int main() { </p> <blockquote> <p> typedef adjacency_list&lt;vecS, vecS, undirectedS, no_property, property&lt;edge_weight_t, double&gt; &gt; graph_t; const unsigned int L = 50; const unsigned int vertexnum = L * L; graph_t graph(vertexnum); unsigned int upper, left; </p> </blockquote> <blockquote> <p> for( unsigned int vertexidx = 0; vertexidx &lt; vertexnum; ++vertexidx ) { </p> <blockquote> <p> upper = ( vertexidx &lt; 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 ); </p> </blockquote> <p> } </p> </blockquote> <p> </p> <blockquote> <p> vector&lt;double&gt; betweenness( num_vertices( graph ) ); brandes_betweenness_centrality( graph, centrality_map( make_iterator_property_map( </p> <blockquote> <p> betweenness.begin(), get( vertex_index, graph ) ) ) </p> </blockquote> <p> ); copy( betweenness.begin(), betweenness.end(), ostream_iterator&lt;double&gt;( cout, " " ) ); return EXIT_SUCCESS; </p> </blockquote> <p> } </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/1398 Trac 1.4.3 Douglas Gregor Thu, 01 Nov 2007 16:16:30 GMT https://svn.boost.org/trac10/ticket/1398#comment:1 https://svn.boost.org/trac10/ticket/1398#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/40645" title="Use unsigned long long for the path count to avoid overflows. Fixes #1398">[40645]</a>) Use unsigned long long for the path count to avoid overflows. Fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/1398" title="#1398: Bugs: brandes_betweenness_centrality doesn't give correct result when ... (closed: fixed)">#1398</a> </p> Ticket