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

Subject: Re: [Boost-users] [Graph] betweenness_centrality - output completed percentage?
From: The Maschine (justthemaschine_at_[hidden])
Date: 2013-01-24 06:24:49

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 <ngedmond_at_[hidden]>
> To: boost-users_at_[hidden]
> Subject: Re: [Boost-users] [Graph] betweenness_centrality - output
>         completed       percentage?
> Message-ID: <F264944D-B0A4-4FB6-BDF0-635E9DCCC199_at_[hidden]>
> 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_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
>