[Networkit] Faster exact diameter calculation
Hamann, Michael (ITI)
michael.hamann at kit.edu
Thu Jul 17 15:31:50 CEST 2014
Hi NetworKit Team,
I've just added an implementation of the iFub-algorithm [0] for the
exact diameter calculation in the Dev branch. Its worst case complexity
is the same as what we did before (n BFS runs), but for most real
networks it is actually very fast. On a network that I generated using
the LFR benchmark (parameters: -N 5000 -k 20 -maxk 50 -mu 0.4 -t1 2 -t2
1 -minc 20 -maxc 100) it needs 16 seconds while the estimated diameter
algorithm needs 30 seconds. Furthermore - in contrast to the algorithm
for the estimated diameter - this algorithm also supports graphs with
multiple connected components (that was not in the original paper but
the generalization was rather simple).
Some questions/tasks for people with some time:
- currently, the starting point is selected by simply using the node
with the maximum degree. According to the authors [1] using their
4-SWEEP algorithm should be even faster in a lot of graphs. If somebody
wants to implement this (shouldn't be that complicated if you want to
mess around with the BFS search): go ahead.
- should we replace the estimated diameter in the properties overview by
the exact one? Do you have any examples where the exact diameter is
slower than the estimated diameter?
- is it maybe possible to enhance the speed of the estimated diameter
algorithm by using the techniques/results from the iFub-algorithm? Or
could it even make sense to use the iFub-algorithm in both cases as the
iFub algorithm also uses a lower and upper bound?
- it would be nice to integrate some of the stuff that I'm currently
doing in the diameter calculation in the BFS and/or Eccentricity
classes. More specifically: getting the maximum distance for networks
with multiple connected components and BFS searches with multiple start
nodes.
Michael
[0] http://piluc.dsi.unifi.it/lasagne/?page_id=43
[1] http://www.sciencedirect.com/science/article/pii/S0304397512008687
More information about the NetworKit
mailing list