[Networkit] Open Problem: Distance Profile via Sampling

Henning Meyerhenke henning.meyerhenke at kit.edu
Fri Aug 14 18:32:49 CEST 2015

Hi Christian,

Is this really open? I can imagine that the routing folks have worked on 
this, e.g. in the context of landmark search or distance oracles. Both 
keywords should point you to relevant literature.


Am 14.08.15 um 15:33 schrieb Christian Staudt:
> 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.
> Best, Chris
> _______________________________________________ NetworKit mailing
> list NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit


Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Juniorprof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150814/1ab53a2a/attachment-0001.p7s>

More information about the NetworKit mailing list