Probabilidad de que dos vértices estén conectados por algún camino en un gráfico dirigido al azar

Defina como un gráfico dirigido al azar ( vértices; colocamos el borde entre dos vértices con probabilidad ). $G(n, p)$ $n$ $p$

¿Cuáles son los resultados conocidos para el siguiente problema?

Fijar dos vértices $v$ y $u$ . ¿Cuál es la probabilidad de que haya al menos una ruta (de longitud como máximo $k$ ) entre $u$ y $v$ ? (claramente el resultado debería ser una función de $n$ , $p$ y $k$ ). El límite superior también funcionaría si no se conoce una respuesta exacta.

graph-theory upper-bounds random-walks random-graphs Daniel
fuente

¿Qué valores de

p

$p$ estás considerando?

Igor Shinkar

@IgorShinkar ¿hace mucha diferencia? No tengo un número específico en mente; a solo una probabilidad

p \in (0, 1)

$p \in (0,1)$ .

Daniel

¿Intentó modificar el enfoque estándar de Erdos-Renyi y, de ser así, cuáles son las dificultades?

usul

¿Has considerado calcular el número esperado de rutas? Eso debería ser mucho más fácil de calcular / estimar debido a la linealidad de las expectativas. También sería un buen indicador de la probabilidad de que haya un camino. es decir, si el número esperado de rutas es 0.01, entonces con una probabilidad de al menos 99% no hay ruta. Y si el número esperado de rutas es 100, entonces supongo que hay una ruta con alta probabilidad.

Thomas

Buena sugerencia Thomas. Solo para asegurarme de que entiendo tu idea: Denota el número de ruta de longitud

con

. ¡El número esperado de ruta de longitud

es (¿verdad?). Defina "X_i = (Y_i> 0)" que muestra el evento de tener una ruta de tamaño entre dos vértices (existencia de ruta). Sé que , que está limitado por . Esto daría un límite superior de en .

i

$i$

Y_{i}

$Y_i$

i

$i$

E [Y_{i}] = (\binom{n - 2}{i - 1}) (i - 1)! p^{i}

$E[Y_i] = { n-2 \choose i-1} (i-1)! p^i$

i (i > 0)

$i (i > 0)$

P (X_{i}) = P (Y_{i} > 0) = \sum_{j = 1}^{\infty} P (Y_{i} = j)

$P(X_i) = P(Y_i > 0) = \sum_{j=1}^{\infty} P(Y_i = j)$

E [Y_{i}] = \sum_{j = 0}^{\infty} j . P (Y_{i} = j)

$E[Y_i] = \sum_{j=0}^{\infty} j. P(Y_i = j)$

\sum_{i = 1}^{k} E [Y_{i}]

$\sum_{i=1}^{k}E[Y_i]$

P (\lor_{i = 1}^{k} X_{i} = 1) = P (\lor_{i = 1}^{k} Y_{i} > 0)

$P( \vee_{i=1}^k X_i =1 ) = P( \vee_{i=1}^k Y_i >0)$

Daniel

Respuestas:

Considere un proceso de exploración BFS, que procede en etapas. Ponga . Dado $k$ $V_0 = \{u\}$ $V_0,\ldots,V_i$ , explore todos los bordes desde hasta (donde es el conjunto de todos los vértices), y configure para que conste de todos los vértices alcanzados de esta manera ; su número tiene una distribución binomial que se puede calcular fácilmente. Después de pasos, verifique si el vértice pertenece a $V_i$ $V \setminus \bigcup_{j=0}^i V_j$ $V$ $V_{i+1}$ $k$ $v$ . $\bigcup_{j=0}^k V_j$

Tenga en cuenta que este proceso es exactamente el mismo tanto en el caso no dirigido como en el dirigido. Por lo tanto, la respuesta, sea cual sea, es idéntica para ambos modelos. Presumiblemente, en el caso no dirigido, la respuesta es conocida y puede consultarse. De lo contrario, puede intentar estimarlo estimando los tamaños y entonces la probabilidad $|V_i|$ quepertenece a. $\frac{1}{n-1} \sum_{i=1}^k |V_i|$ $v$ $\bigcup_{i=1}^k V_i$

Yuval Filmus
fuente

¿Por qué el voto negativo?

Yuval Filmus

esto daría una probabilidad de una trayectoria de longitud exactamente k, no como máximo k; ¿Es eso correcto?

Daniel

Como está escrito, es para la variante "como máximo".

Yuval Filmus