Modelo gráfico aleatorio

Question

Cuando decimos que en un gráfico aleatorio agregamos un borde con una cierta probabilidad fija, ¿qué queremos decir realmente?

Por ejemplo, si la probabilidad es 0.5, eso significa que podemos agregar dos bordes en un gráfico porque 0.5+0.5 = 1.

Answer 1

Supongamos que desea calcular el gráfico aleatorio $ G (n, p) $ que es el gráfico con $ n $ vértices donde cada borde se agrega con probabilidad $ p. $ $

Supongamos que tiene una moneda que le da a Tails con probabilidad $ P $ y cabezas con probabilidad de $ 1-P. $

Entonces, ¿qué haces? Elige 2} $ volteas tu moneda. Si se produce, agregue el borde $ (i, j) $ a su gráfico, de lo contrario no lo hace.

Answer 2

En el modelo aleatorio $ g (n, p) $, cada uno de los bordes $ binom {n} {2} $ se agrega al gráfico con probabilidad $ P $ independientemente. Eso significa que si considera dos bordes, ambos están en el gráfico con probabilidad $ P^2 $, no $ 2p $.

Answer 3

Además de lo que se dice, que es correcto, puede construir un gráfico aleatorio $ G (N, P) $ por $ 0 leq p leq 1 $ de la siguiente manera:

Suponga que tiene un conjunto de vértices $ V $ y bordes vacíos $ E $. Por cada $ V $ en $ v $: por cada $ u $ en $ v $ (donde $ u> v $ con respecto a algún pedido total entre los nodos de $ v $): genere un número aleatorio uniforme $ r $ $ r en [0,1] $. If ($ r leq p $) Luego incluya el borde $ (v, u) $ y $ (u, v) $ a $ e $.

Esto genera un gráfico aleatorio $ g = (v, e) $ denotado $ g (n, p) $ donde $ | v | = n $. Sin embargo, este es un gráfico dirigido. Si desea convertirlo en un gráfico dirigido, que como ese caso no sigue la definición, agregue solo el gráfico $ (v, u) $.