The outer loop of betweenness centrality is a loop over all the vertices in the graph with each used as the source of a shortest paths computation. If you want to see how far along the algorithm is you can just instrument the "for (boost::tie(s, s_end) = vertices(g); s != s_end; ++s)" in brandes_betweenness_centrality_impl(). Note that you don't actually need to count shortest paths from *every* vertex in the graph to get a good approximation of betweenness centrality, check out this paper [1]. Sampling the vertices in the graph and counting shortest paths from a subset of them should significantly speed up betweenness centrality if a (relatively good) approximation will work for your application.

On Jan 22, 2013, at 8:04 AM, Tasos wrote:

Hello all,

I calculate the betweenness-centrality of a large graph
(V:150k, E:500k, boost::adjacency_list<boost::vecS, boost::vecS,
boost::undirectedS,) with boost::brandes_betweenness_centrality
and I can find how to get a indication of the 'completed'
part of the algorithm.

For example this graph took 1h:38m (single thread 10.8 iMac 3.4ghz)
to complete but in order to be able to know the execution time
of larger graph im a bit lost...

On "one to all" BFS you know how many vertices you
have left but this algorithm seems to me lacking a custom
visitor or something in order to output some data.

Any ideas as Im really new to boost.graph?

Thanks a lot,
Tasos

_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users