# Mean and median distance in unweighted graph

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?

• 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.
– D.W.
Dec 7, 2016 at 22:41
• 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.
– Tom
Dec 7, 2016 at 23:01
• Can you share with us the source of this problem/exercise?
– D.W.
Dec 7, 2016 at 23:13
• For diameter, see Theorem 1 and the ​ "We prove Theorem 1 by showing that an ... reason." ​ part of that paper. ​ ​ ​ ​
– user12859
Dec 8, 2016 at 5:20

(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.

• Why is the median distance necessarily an integer? ​ ​
– user12859
Dec 8, 2016 at 2:36
• @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?
– D.W.
Dec 8, 2016 at 3:44
• {1,2} is a set of integers whose median is not an integer. ​ ​
– user12859
Dec 8, 2016 at 3:45
• @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).
– D.W.
Dec 8, 2016 at 3:46
• 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. Jan 18, 2019 at 22:04