[Networkit] new diameter algorithm - benchmark
michael.hamann at kit.edu
Tue Feb 16 16:47:38 CET 2016
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?
More information about the NetworKit