Probability that the distance from some source vertex to any other vertex is at most exactly $l$ in a random graph?

250 Views Asked by At

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 our random graph has the following property: we can start at the source and go to any other vertex in the graph in at most exactly $l$ edges, i.e., there is at least some vertex $v\in G$ such that the shortest distance between $u$ and $v$ is $l$ and there is no vertex $v'\in G$ such that the shortest distnace between $u$ and $v'$ is more than $l$.

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.

1

There are 1 best solutions below

7
On BEST ANSWER

It seems to me that you want an exact expression for this probability. Here is one such formula albeit it does not have a nice closed form. Fix some vertex $u$ in $G(n,p)$. Let's define $d(u) = \max_v d(u,v)$, where $d(u,v)$ is the distance between $u$ and $v$. So you are interested in $P(d(u) \leq \ell)$ for any $\ell \in [1,n-1]$.

Let $$A_\ell:=\{(k_1, ..., k_\ell): k_i \geq 0, k_1+...+k_\ell = n-1, \text{ if }k_i=0, \text{ then } k_{i+1}=...=k_{\ell}=0\}, $$ and $k_0:=1$.

Then $$P(d(u) \leq \ell) = \sum_{(k_1,...k_\ell)\in A_{\ell}} {n-1 \choose k_1, k_2, ..., k_\ell} \prod_{i=1}^{\ell} \left( 1 - \left( 1- p\right)^{k_{i-1}}\right)^{k_i} (1-p)^{(1+k_1+...+k_{i-2})k_i},$$ with the understanding that the last factor is defined to be 1 for $i=1$.

Why? Run a breadth-first search starting from $u$. Let $\mathcal{L}_1, ..., \mathcal{L}_{n-1}$ be the (random) set of vertices found at each level; formally $\mathcal{L}_i:=\{v \in G(n,p): d(u,v)=i\}$. Suppose that $L_1,...,L_{n-1}$ is a partition of $[n]\setminus \{u\}$ so that if $|L_j|=0,$ then $|L_{j+1}|=...=|L_{n-1}|=0$. So $$ P((\mathcal{L}_1,...,\mathcal{L}_{n-1})=(L_1,...,L_{n-1}))= \prod_{i=1}^{n-1} \left( 1 - \left(1-p\right)^{|L_{i-1}|}\right)^{|L_i|}(1-p)^{(1+k_1+...+k_{i-2})k_i}. $$ This is because we need every vertex of $L_{i}$ to be adjacent to at least one vertex of $L_{i-1}$ and NOT adjacent to any vertex of $L_0, ..., L_{i-2}$. To finish off the proof, the events $\vec{\mathcal{L}} = \vec{L}$ and $\vec{\mathcal{L}}=\vec{L}'$ are disjoint if $\vec{L} \neq \vec{L}'$. Adding over all possible such sequences yields the formula above.

EDIT: I forgot the $(1-p)^{(1+...+k_{i-2})k_i}$ term in the original post.