Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$ and call it the source. I am interested in the probability that there is no vertex (in the whole graph) at a distance larger than $d$ away from the source.

Distance $d$ between $u\in G$ and $v\in G$ is measured by the number of edges between $u$ and $v$ along a shortest path.


Obviously, we assume that $d$ is finite. First, we must establish a generating function for $G(n,p)$. The probability that a vertex $v$ has degree $k$ is $p_k = \dbinom{n-1}kp^k(1-p)^{n-1-k}$ from the argument that we need to pick $k$ from $n-1$ and each of those have to be existing edges while the other edges should not exist.

Now we can approximate this binomial distribution by a Poission distribution for large $n$ with $p_k \approx e^{-c}\frac{c^k}{k!}$ where $c = p(n-1)$ or your expected number of neighbours.

Now that we have a generating function for a degree distribution, we can proceed as follows. Let $g_0(z) = \sum_{k = 0}^{\infty} p_kz^k$. This problem reduces to finding the degree distribution of a $d+1$th neighbor of a chosen vertex $v$ with degree $k$ in $G$.

It turns out that the degree distribution of the neighbour of vertex $v$ is $g_1(z) = \frac{g_0'(z)}{g_0'(1)}$. Furthermore, we can also prove that the degree distribution of $2$nd neighbors is $g_0(g_1(z))$ and it turns out that the degree distribution of the $d+1$th neighbour is $g_{d+1}(z) = g_{d}(g_{d-1}( \cdots g_1(g_0(z)) \cdots ))$.

Then we want the expected number of $d+1$th neighbors to be less than $1$. This value is just $g_{d+1}'(1)$.

  • $\begingroup$ Hey, did you mean $g^{(d+1)}=g_0(g_1(\ldots (g_1(z))\ldots))$ instead? $\endgroup$ May 9 '14 at 1:52
  • $\begingroup$ For anyone else who stumbles across: the answer given above is better explained in the following paper: arxiv.org/pdf/cond-mat/0007235v2.pdf. Thanks. $\endgroup$ May 9 '14 at 1:53
  • $\begingroup$ If the edge probability $p$ is large enough, then the degree of a generic vertex is not well approximated by a Poisson distribution. Poisson approximation works when $np=c,$ where $c$ is a constant (which was the range looked at in that paper). However, in this range, the probability that $G(n,p)$ is connected is exponentially small. $\endgroup$
    – D Poole
    May 13 '14 at 14:09
  • $\begingroup$ Actually, @Sandeep, $g_{d+1}^{'}(1)$ doesn't make sense. If $g_{d+1}(z)$ is the degree distribution of $d+1$th neighbors, then $g_{d+1}^{'}(1)$ is $\Sigma_{k=0}^{\infty}k p_k z^{k-1}$ which is not a probability, but the average number of $d+1$th neighbors. What am I missing? $\endgroup$ Aug 6 '14 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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