Message: 5
Date: Wed, 23 Jan 2013 20:54:16 -0500
From: Nick Edmonds <ngedmond@cs.indiana.edu>
To: boost-users@lists.boost.org
Subject: Re: [Boost-users] [Graph] betweenness_centrality - output
completed percentage?
Message-ID: <F264944D-B0A4-4FB6-BDF0-635E9DCCC199@cs.indiana.edu>
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<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