[Networkit] All pairs shortest path

Matteo Riondato matteo at cs.brown.edu
Tue Dec 13 14:26:53 CET 2016


> On Dec 13, 2016, at 2:04 PM, Elisabetta Bergamini <elisabetta.bergamini at kit.edu> wrote:
> 
> HI Christian,
> 
> what are your running time requirements?
> I tried to generate a random weighted graph with 1000 nodes and about 500K edges and APSP took seconds on my laptop.
> Would that work for you? There are no heuristics for approximating shortest paths distances in NetworKit at the moment. However, a very simple one could be to just select a set L of central nodes (e.g. node with highest degree or high approx. betweenness), compute a SSSP from each of them and approximate the distance between any two nodes (u, v) as min_{l in L} d(u, l) + d(l, v).

Yes, this can be a good heuristic. There’s a paper by Edith Cohen et al. at COSN’14 (IIRC) to compute approximate closeness centrality that exploits a similar idea: they actually chose the nodes uniformly at random and then have the concept of a pivot p(v) for each node v (p(v) is the sampled node closest to v) that they use for better estimation.

Matteo




More information about the NetworKit mailing list