5
$\begingroup$

I have a very large graph of ~7 million vertices and ~100 million edges. One dfs run in my current implementation runs in 30 seconds. The graph is an unweighted directed strongly connected graph.

I need to find the mean and median distances of the graph (median and mean distances over all shortest-path distances of the graph). I need the exact mean/median, not an approximation. This problem must be related to all-pairs shortest paths. But the only algorithms I know of for this problem are: Floyd Warshall, Dijkstra starting from each vertex, and Breadth First Search starting from each vertex. However, their running time is $\Omega(V^2)$ for all three of these algorithms, so for such a large graph they are too slow.

Can this problem be solved in linear or linearithmic time? If not, what is the fastest algorithm for this problem, in asymptotic complexity?

$\endgroup$
4
  • 1
    $\begingroup$ 1. I wonder if research on "distance oracles" or preprocessing a graph to support fast distance queries might be useful somehow. See, e.g., cstheory.stackexchange.com/q/8703/5038, cstheory.stackexchange.com/q/11518/5038, cstheory.stackexchange.com/q/8911/5038. Approximate distance oracles probably won't be useful, and I don't know if much is known about exact oracles. 2. Is the diameter of this graph small, compared to $V$? Is the mean/median small compared to $V$? I don't know if that might help design a faster algorithm, if it is known/expected to be small. $\endgroup$
    – D.W.
    Dec 7, 2016 at 22:41
  • $\begingroup$ Yes, it is very short (though I kinda supposed to find it myself too) - I was also going to ask the next question here about diameter =) But the graph diameter from their data = 15. But I kinda dont know how it can be useful at all. Thx for links though. $\endgroup$
    – Tom
    Dec 7, 2016 at 23:01
  • 1
    $\begingroup$ Can you share with us the source of this problem/exercise? $\endgroup$
    – D.W.
    Dec 7, 2016 at 23:13
  • $\begingroup$ For diameter, see Theorem 1 and the ​ "We prove Theorem 1 by showing that an ... reason." ​ part of that paper. ​ ​ ​ ​ $\endgroup$
    – user12859
    Dec 8, 2016 at 5:20

1 Answer 1

3
$\begingroup$

(This is not a full answer.)

The median distance is necessarily an integer [footnote 1]. Therefore, it might be possible to use an approximation algorithm for the median to compute the exact median, if the approximation is sufficiently precise.

Suppose the true median is $\xi$. Then if we can efficiently compute a $1+1/3\xi$-approximation to the median, we can reconstruct the exact median from that.

I suspect it is possible to get a $\tau$-approximation to the median efficiently through random sampling. In particular, consider the following procedure:

  • Repeat $k$ times: in the $i$th iteration, pick a random vertex $v_i$, compute single-source shortest paths from $v_i$ to every vertex, and find the distribution of these distances.

  • Aggregate these distributions and output the median of this aggregated distribution.

One might hope to get an approximation whose quality increases rapidly with $k$, and where if we want a constant approximation factor $\tau$, then a constant $k$ suffices. I have no proof that this is possible, though.

We can consider a simpler situation, where given an integer $x$ we are trying to approximately count the fraction of distances that are at most $x$. If the fraction of such distances is approximately $1/2$ (e.g., because $x$ is approximately the median), then one approach is random sampling: repeat $k$ times where we pick a random pair of vertices $u,v$ and compute the distance from $u$ to $v$ (say using BFS), then count what fraction of those $k$ distances are at most $x$. The additive error is typically about $1/2\sqrt{k}$; it exceeds $c/\sqrt{k}$ with probability exponentially small in $c$ (it's basically the probability of a Gaussian being more than $2c$ standard deviations away from the mean). Thus, we can get a $1+\epsilon$-approximation to this count using $O(1/\epsilon^2)$ iterations. Each iteration takes at most $O(E)$ time, so with $O(E/\epsilon^2)$ time we can get a $1+\epsilon$-approximation to this count. The probability that our approximation is wrong can be made exponentially small; an error probability of $1/2^{100}$ is so small as to be negligible in practice (e.g., it is smaller than the probability of a cosmic ray causing a bitflip error that causes an error in your code), and this will increase the running time by only a constant factor (say, 100, or something like that). In this case it might be sufficient to also take $\epsilon$ to be a small constant.

Intuitively, it feels like if we can get a good approximation to this count, it might be possible to extend this to a good approximation to the median. For instance, if we hypothesize that the median is $x$, we can count the fraction of distances that are $\le x-1$, the fraction that are $\le x$, and the fraction that are $\le x+1$. If $x$ is indeed the median, hopefully the first fraction will be noticeably smaller than $1/2$ and the latter fraction will be noticeably larger than $1/2$. I don't know how to turn this into an algorithm that I can prove will always work on all graphs, but I suspect this might work well enough in practice.


Computing the (exact) mean seems like it might be harder, as the mean isn't necessarily an integer.


Footnote 1: The median is either an integer or halfway between two integers. In the latter case, the rest of the answer carries through if you divide everything by two.

$\endgroup$
5
  • $\begingroup$ Why is the median distance necessarily an integer? ​ ​ $\endgroup$
    – user12859
    Dec 8, 2016 at 2:36
  • $\begingroup$ @RickyDemer, the median of a bunch of integers is always an integer. Each distance is an integer (since we're dealing with an unweighted graph), and the question asks us to compute the median of $V^2$ of these integers. Or have I overlooked something? $\endgroup$
    – D.W.
    Dec 8, 2016 at 3:44
  • $\begingroup$ {1,2} is a set of integers whose median is not an integer. ​ ​ $\endgroup$
    – user12859
    Dec 8, 2016 at 3:45
  • $\begingroup$ @RickyDemer, I guess it depends how you want to define the median. Under one definition, the median of {1,2} is either 1 or 2 (they're both medians). Under a different definition, the median of {1,2} is 1.5. If you prefer the former definition, the median is always an integer. If you prefer the latter definition, the median is always an integer or a half-integer (i.e., integer plus 0.5), and the rest of the answer carries through (dividing everything by 2). $\endgroup$
    – D.W.
    Dec 8, 2016 at 3:46
  • $\begingroup$ Although it makes sense to define the median in other ways, the standard is to compute the mean of the two "median" values. I would just rewrite that first paragraph with the details of your comment, because it sounds weird. $\endgroup$ Jan 18, 2019 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.