4
$\begingroup$

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$. I want to know what is the expected number of vertices a distance $k$ away (where distance means the shortest distance). I can only figure out that we expect there to be $(n-1)p$ vertices a distance 1 away since each of the possible $(n-1)$ edges outgoing from $u$ have probability $p$ of existing, but I am having trouble generalizing from this local property. Maybe someone can handle the task or perhaps point me in the right direction via a paper?

If it makes it easier, assume that $G$ is connected (as it almost surely is as $n\rightarrow \infty$, which is the case I am interested about). As a subproblem of almost equal importance, I would in particular like to know what is the expected longest shortest distance from vertex $u$ and how many vertices are away from vertex $u$ at that distance (subproblem with the maximum possible $k$).

Note: (1) The graph does not have a bound on the degree of the vertex (there could be as many as $n-1$ adjacent vertices to $u$).

$\endgroup$
  • $\begingroup$ This problem has a lot of symmetry. I like to think of it as the complete graph with weights $p$ on the edges. I think the assumption that $G$ is connected is probabilistically speaking unnatural. $\endgroup$ – Patrick Da Silva Jan 5 '14 at 5:12
  • $\begingroup$ There are some easy $k$'s where you can compute explicitly ; for $k = n-1$, the only way that a vertex is at a distance $n-1$ is if you have a path graph ; for there must be a path of length $n-1$ from $u$ to some vertex $v$, hence you have a sequence $$ u= u_0, e_1 = \{u_0,u_1\}, e_2 = \{u_1,u_2\}, \cdots , e_{n-1} = \{ u_{n-1},u_n\}, \quad u_n = v. $$ Any edge outside the set $\{e_1,\cdots,e_{n-1}\}$ induces a path of length shorter than $n-1$ between $u$ and $v$, so you get a path graph. Computing the expectation becomes combinatorics in this case. $\endgroup$ – Patrick Da Silva Jan 5 '14 at 5:16
  • $\begingroup$ There are $\binom n2$ possible edges and $n-1$ of them must be in the graph, so the probability that a particular path happens is $p^{n-1} (1-p)^{\binom n2 - (n-1)}$ ; the number of possible paths is simply $n!$, i.e. the number of way to order $u_1,\cdots,u_n$. Your final answer is $$ n! p^{n-1} (1-p)^{\binom n2 - (n-1)} = n! p^k (1-p)^{\binom n2 - k}. $$ $\endgroup$ – Patrick Da Silva Jan 5 '14 at 5:19
  • 1
    $\begingroup$ @PatrickDaSilva, oh okay. I see what you were continuing your proof which you started in the comment prior. Good special case, which might help in the general case. Thanks. $\endgroup$ – bourbaki4481472 Jan 5 '14 at 5:27
  • 1
    $\begingroup$ I don't think it would be too hard to obtain a formula for the expected number of vertices at distance at most $k$ (and then compute the $k$ case minus the $k-1$ case) by simply averaging the probability that a random path between $u$ and some vertex $v$ of length $k$ happens. Otherwise I don't see how this could be solved. $\endgroup$ – Patrick Da Silva Jan 5 '14 at 5:30
4
$\begingroup$

Let $\lambda=np$. Then the average distance $k$ between two randomly picked vertices from the giant component is $$ k\sim \frac{\log n}{\log \lambda}, $$ given that the giant component exists ($\lambda>1$). A proof can be found in, e.g., Durrett's Random graph dynamics.

This result implies that the actual number for your first question is $$ \lambda^k. $$ However, this only works if $pn\to\lambda<\infty$ when $n\to\infty$. What about the case $p=const$? Here is an exercise: Show that the diameter of the E-R random graph in this case is 2 a.a.s.

For the diameter (the largest among the shortest paths) the question is more subtle. A nice review is given in Complex Graphs and Networks bu Lu and Chung, and the answer depends on the parameters.

$\endgroup$
  • $\begingroup$ It's interesting that you get $\lambda^d$, because the cases $k=1$ and $k=n-1$ have a geometric random variable flavor. $\endgroup$ – Patrick Da Silva Jan 5 '14 at 5:55
  • $\begingroup$ @PatrickDaSilva The results I state are asymptotic. (I changed my $d$ for $k$ as in the original question). I do not quite get what you calculate in the case "$k=n-1$". $\endgroup$ – Artem Jan 5 '14 at 6:04
  • $\begingroup$ @Artem, sorry, what is "a.a.s."? $\endgroup$ – bourbaki4481472 Jan 5 '14 at 6:11
  • 1
    $\begingroup$ @ijkilchenko Ups, apologies. Asymptotically almost surely. Another terminology is w.h.p. (with high probability). Probability of something going to 1 when $n\to\infty$ $\endgroup$ – Artem Jan 5 '14 at 6:13
  • $\begingroup$ Are you having an issue with a specific detail in my proof? All I can do at this point is either answer your specific questions with regards to it or put more details in a separate answer. $\endgroup$ – Patrick Da Silva Jan 6 '14 at 11:05

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.