[Networkit] Open Problem: Distance Profile via Sampling
henning.meyerhenke at kit.edu
Fri Aug 14 18:32:49 CEST 2015
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
> 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
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)
Juniorprof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing
KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
More information about the NetworKit