2

Random Geometric graphs (graphs where n points are placed at random in the unit square, and two nodes are connected with probability 1 if $r \leq r^*$) are known to percolate iff:

$$\pi r^2 = \frac{\log{n} + c\left(n\right)}{n}$$

This implies that the diameter of the graph is $\Theta\left(\sqrt{\frac{\pi n}{\log{n}}}\right)$.

Is it known what the distribution of expected path length between any two nodes is for this graph is, assuming we are in the supercritical regime, especially for fixed $n$?

Misha Lavrov
  • 142,276
Tom Kealy
  • 282
  • What do you mean by the ``distribution of expected path length"? Do you the distribution of the path length between generic vertices $v$ and $w$ or an asymptotic expression for the expected path length between generic $v$ and $w$? I think the latter is trivially infinite as long as $r<1/\sqrt{2},$, because there is a positive, although vanishing w.r.t. $n$, probability that there is not a path between $v$ and $w$, which forces the expected path length to be infinite. – D Poole Dec 18 '13 at 16:17
  • @DPoole If I have a G(n,r), with some fixed n, what is the expected number of hops between to vertices, $u$, $v$? I.e. do I go 10 hops or 5 etc. If it's finite, is the distribution known? – Tom Kealy Dec 18 '13 at 16:35
  • It seems like you wish to know the expected value of the distance between $u$ and $v$ conditioned on the event there is a path between $u$ and $v$. I'm not too familiar with random {\it geometric} graphs, but in the models $G(n,p)$ and $G(n,m)$, the asymptotic distribution of the distance between generic vertices $u$ and $v$ is $(1+o(1))\text{diameter}(G(n,\circ)),$ for a wide range of the parameter values $m$ and $p$. However, in geometric random graphs, I imagine that the distribution heavily depends on $||u-v||$ (distance in $\mathbb{R}^d$). – D Poole Dec 18 '13 at 18:37
  • Yes that's exactly what I'm interested in. – Tom Kealy Dec 18 '13 at 19:21

0 Answers0