[Networkit] All pairs shortest path

Christian Staudt christian.staudt at kit.edu
Wed Dec 14 19:57:42 CET 2016


> On 13 Dec 2016, at 15:04, Elisabetta Bergamini <elisabetta.bergamini at kit.edu> wrote:
> 
> 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?

Great, then the case is probably solved if the graph stays so small. Thanks for testing Elisabetta.

I think APSP needs to be imported into the distance module. I can do this later, then it looks presentable to my client.

Question: APSP.getDistances() documentation says: "Returns a vector of vectors of weighted distances from the source node, i.e. the
 	 	length of the shortest path from the source node to any other node.”

What is the source node? Does this make sense?

> 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).
> Best,
> 
> Elisabetta



> 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

Thanks for the ideas. Let me check if the problem size will actually grow, then we can think further in this direction.

Chris



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20161214/efdddff6/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20161214/efdddff6/attachment.sig>


More information about the NetworKit mailing list