Re: [Boost-users] [Graph] betweenness_centrality - output completed percentage?

Hi Nick, Thanks a lot for both comments! We currently use an "approximation/sub sampling" algorithm done 10years ago by a colleague but its take 10 times more than BGLs and Im not sure its statistically verified. The paper seems really good. About the brandes_betweenness_centrality_impl(), I suppose you are implying that I have to change the boost.graph header file directly? Right? Best, Tasos

Message: 5 Date: Wed, 23 Jan 2013 20:54:16 -0500 From: Nick Edmonds To: boost-users@lists.boost.org Subject: Re: [Boost-users] [Graph] betweenness_centrality - output completed percentage? Message-ID: Content-Type: text/plain; charset="us-ascii"

Hi Tasos,

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.

Cheers, Nick

[1] http://www.cc.gatech.edu/~bader/papers/ApproxBC.html

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

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