[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