[Networkit] Open Problem: Distance Profile via Sampling

Christian Staudt christian.staudt at kit.edu
Fri Aug 14 15:33:47 CEST 2015

Hi all, can I get some suggestions on an open problem?

Imagine the following “distance profile” of a graph: For all pairs of nodes (u,v), compute the distance d(u,v) and plot the resulting distribution of distances. This is also sometimes called a “hop plot”.

Now, doing this for all pairs clearly doesn’t scale, but if we are just interested in the shape of the distribution, we do not need to know all distances. I want to sample distances d(u,v) in a complex network so that

a) the result is representative (i.e. the sampled distribution of distances is qualitatively the same as the full distribution)
b) the computation is efficient (i.e. the number of graph traversals performed is small)

Algorithm idea: x times pick some node u uniformly at random, perform a single-source shortest path search, then y times pick some node v and store distance d(u,v). Then, what should x and y be?

Would be thankful for any suggestions. By the way, seems like there is some connection to approximation of betweenness.

-------------- 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: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150814/a9aa704b/attachment.sig>

More information about the NetworKit mailing list