[Networkit] new diameter algorithm - benchmark

Michael Hamann michael.hamann at kit.edu
Tue Feb 16 16:47:38 CET 2016


Hi,

thank you for the benchmark, Chris.

On Tuesday 16 February 2016 16:17:12, Christian Staudt wrote:
> new: SumSweep

There is one thing I want to add here: What I implemented is not exactly 
SumSweep but a variation of it. I first implemented SumSweep without one detail 
that is not so easy to implement in NetworKit and then noticed that on several 
networks it did not perform that well. Then I started modifying some parts of 
the heuristics in order to improve that. However from some first tests with a 
comparison of the number of BFS it seems that my changes are beneficial for 
road networks, but not for complex networks. Therefore it is possible that a 
full implementation of the original algorithm is better. I did not spend too 
much time on that implementation and experimentation as I simply needed 
something that is more robust than iFub and faster as I wanted to include a 
broader range of networks in some experiments.

We plan to supervise a bachelor's or master's thesis on the further 
development of the algorithm, in particular the question how to parallelize 
the algorithm (note that iFub was parallelized in our implementation while 
SumSweep is not). If you are interested in that topic or know somebody who is, 
please write Elisabetta or me.

> Result: For typical complex networks, they are basically equally fast.
> SumSweep just has much better worst-case behavior, which means it will also
> work on street-network like graphs.

How do these running times deal with parallelization?

Best regards,
Michael



More information about the NetworKit mailing list