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

Subject: Re: [Boost-users] [Graph] betweenness_centrality - output completed percentage?
From: Nick Edmonds (ngedmond_at_[hidden])
Date: 2013-01-23 20:54:16

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<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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users