[Networkit] Algorithms based on shortest path aggregation are *embarrassingly* parallel

Arie Slobbe aslobbe at macalester.edu
Wed Sep 9 16:28:46 CEST 2015


for centrality.ApproxCloseness, the largest gains from parallelization
would come from replacing line 36 ("for (node s : sampledNodes") { ) with a
parallel equivalent. But I'm no expert on parallel computing and I would
sure appreciate some help with the implementation!

On Wed, Sep 9, 2015 at 7:54 AM, Christian Staudt <christian.staudt at kit.edu>
wrote:

> p.s. There is one more way to cut the running time here: Max and I have
> been working on implementing a modified BFS algorithm which can be 2-4
> times faster on complex networks. To be announced soon.
>
> On 09 Sep 2015, at 14:46, Christian Staudt <christian.staudt at kit.edu>
> wrote:
>
> > Hi developers,
> > centrality measures based on shortest paths (like betweenness, closeness
> etc.) are relevant, but also expensive to compute. Doing many traversals of
> a large graph takes long, but parallelizing them and aggregating the
> results is probably easy.
> >
> > The following algorithms are currently not parallel:
> >
> > centrality.ApproxBetweenness2
> > centrality.ApproxCloseness
> >
> >
> > So for those working on the subject, can you please parallelize these
> and future similar algorithms?
> >
> > Best,
> > Chris
> >
> >
> >
> > _______________________________________________
> > NetworKit mailing list
> > NetworKit at ira.uni-karlsruhe.de
> > https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150909/ac4f9e45/attachment-0001.html>


More information about the NetworKit mailing list