Probabilidad de que no haya ningún vértice a una distancia mayor que $d$ ¿se aleja de la fuente en el gráfico aleatorio?

Question

Dado un grafo aleatorio (no dirigido y no ponderado) $G$ en $n$ vértices donde cada una de las aristas tiene una probabilidad igual e independiente $p$ de los existentes (véase Modelo Erdos-Rényi ). Fijar algún vértice $u\in G$ y llamarlo la fuente. Me interesa la probabilidad de que no haya ningún vértice (en todo el gráfico) a una distancia mayor que $d$ lejos de la fuente.

Distancia $d$ entre $u\in G$ y $v\in G$ se mide por el número de aristas entre $u$ y $v$ a lo largo de un camino más corto.

Answer 1

Obviamente, suponemos que $d$ es finito. En primer lugar, debemos establecer una función generadora para $G(n,p)$ . La probabilidad de que un vértice $v$ tiene grado $k$ es $p_k = \dbinom{n-1}kp^k(1-p)^{n-1-k}$ del argumento de que tenemos que elegir $k$ de $n-1$ y cada una de ellas tienen que ser aristas existentes mientras que las otras aristas no deben existir.

Ahora podemos aproximar esta distribución binomial por una distribución de Poission para grandes $n$ con $p_k \approx e^{-c}\frac{c^k}{k!}$ donde $c = p(n-1)$ o su número previsto de vecinos.

Ahora que tenemos una función generadora para una distribución de grados, podemos proceder como sigue. Sea $g_0(z) = \sum_{k = 0}^{\infty} p_kz^k$ . Este problema se reduce a encontrar la distribución de grados de un $d+1$ vecino de un vértice elegido $v$ con grado $k$ en $G$ .

Resulta que la distribución de grados del vecino del vértice $v$ es $g_1(z) = \frac{g_0'(z)}{g_0'(1)}$ . Además, también podemos demostrar que la distribución de grados de $2$ y vecinos es $g_0(g_1(z))$ y resulta que la distribución de grados del $d+1$ El vecino es $g_{d+1}(z) = g_{d}(g_{d-1}( \cdots g_1(g_0(z)) \cdots ))$ .

Entonces queremos el número esperado de $d+1$ vecinos sea inferior a $1$ . Este valor es sólo $g_{d+1}'(1)$ .