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

Christian Staudt christian.staudt at kit.edu
Wed Sep 9 14:54:27 CEST 2015


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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150909/44232371/attachment.sig>


More information about the NetworKit mailing list