Modelo de Erdős-Rényi

En el campo matemático de la teoría de grafos, el modelo de Erdős–Rényi se refiere a uno de los dos modelos estrechamente relacionados para generar grafos aleatorios o la evolución de una red aleatoria. Estos modelos reciben su nombre de los matemáticos húngaros Paul Erdős y Alfréd Rényi, quienes introdujeron uno de los modelos en 1959. Edgar Gilbert introdujo el otro modelo de manera contemporánea e independiente de Erdős y Rényi. En el modelo de Erdős y Rényi, todos los grafos en un conjunto de vértices fijos con un número fijo de aristas tienen la misma probabilidad. En el modelo introducido por Gilbert, también llamado el modelo de Erdős–Rényi–Gilbert, cada arista tiene una probabilidad fija de estar presente o ausente, independientemente de las otras aristas. Estos modelos se pueden utilizar en el método probabilístico para demostrar la existencia de grafos que satisfacen varias propiedades, o para proporcionar una definición rigurosa de lo que significa que una propiedad se cumple para casi todos los grafos.

Existen dos variantes estrechamente relacionadas del modelo de gráfico aleatorio de Erdős–Rényi.

• En el ${\displaystyle G(n,M)}$ modelo, un gráfico es elegido uniformemente al azar de la colección de todos los gráficos que tienen ${\displaystyle n}$ nodos y ${\displaystyle M}$ bordes. Los nodos se consideran etiquetados, lo que significa que los gráficos obtenidos entre sí al permutar los vértices se consideran distintos. Por ejemplo, en el ${\displaystyle G(3,2)}$ modelo, hay tres gráficos de dos niveles en tres vértices etiquetados (uno para cada elección del vértice medio en un camino de dos niveles), y cada uno de estos tres gráficos se incluye con probabilidad ${\fnMicroc} {1}{3}}$.
• En el ${\displaystyle G(n,p)}$ modelo, un gráfico se construye conectando nodos etiquetados al azar. Cada borde está incluido en el gráfico con probabilidad ${\displaystyle p}$, independientemente de cada otro borde. Equivalentemente, la probabilidad de generar cada gráfico que tiene ${\displaystyle n}$ nodos y ${\displaystyle M}$ bordes es $${\displaystyle p^{M}(1-p)^{n \choose 2}-M}$$ El parámetro ${\displaystyle p}$ en este modelo se puede considerar como una función de ponderación; como ${\displaystyle p}$ aumentos ${\displaystyle 0}$ a ${\displaystyle 1}$, el modelo se vuelve cada vez más probable que incluya gráficos con más bordes y menos y menos probable que incluya gráficos con menos bordes. En particular, el caso ${\displaystyle p={\tfrac {1}{2}}}$ corresponde al caso donde todo ${\displaystyle 2^{\binom {n}{2}}$ gráficos en ${\displaystyle n}$ vertices son elegidos con igual probabilidad.

El comportamiento de los gráficos aleatorios se estudia a menudo en el caso en que ${\displaystyle n}$, el número de vértices, tiende a infinito. Aunque ${\displaystyle p}$ y ${\displaystyle M}$ puede ser fijado en este caso, también pueden ser funciones dependiendo de ${\displaystyle n}$. Por ejemplo, la afirmación de que casi todos los gráficos en ${\displaystyle G(n,2\ln)/n)}$ es conectado significa que, como ${\displaystyle n}$ tiende a infinito, la probabilidad de que un gráfico en ${\displaystyle n}$ vertices con probabilidad de borde ${\displaystyle 2\ln(n)/n}$ está conectado tiende a ${\displaystyle 1}$.

El número esperado de bordes en G()n, p) es ${\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\\\\fnMicrosoft {\\\\fnMicrosoft {\\fnMicrosoft {\\\\\\\\\fnMicrosoft {\\\\fnMicrosoft {\\\\fnMicrosoft}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fnMin {n}{2}p}$, y por la ley de números grandes cualquier gráfico en G()n, p) casi seguramente tendrá aproximadamente estos muchos bordes (siempre que el número esperado de bordes tiende a la infinidad). Por lo tanto, una heurística ruda es que si pn² → ∞, entonces G()n,p) debe comportarse de forma similar a G()n, MCon ${\displaystyle M={\tbinom {n}{2}p}$ como n aumenta.

Para muchas propiedades gráficas, este es el caso. Si P es cualquier propiedad grafica que es monótona con respecto al orden del subgrafo (que significa que si A es un subgrafo de B y B satisfizo PEntonces A satisfacer P , entonces las declaraciones "P para casi todos los gráficos en G()n, p)" y "P para casi todos los gráficos en ${\displaystyle G(n,{\tbinom {n}p)}$" son equivalentes (proporcionados pn² → ∞). Por ejemplo, esto sostiene si P es la propiedad de estar conectado, o si P es propiedad de contener un ciclo Hamiltoniano. Sin embargo, esto no se mantendrá necesariamente para propiedades no monotonas (por ejemplo, la propiedad de tener un número uniforme de bordes).

En la práctica, el modelo G(n, p) es el que se utiliza más comúnmente en la actualidad, en parte debido a la facilidad de análisis que permite la independencia de las aristas.

Con la notación anterior, un gráfico en G()n, p) tiene en promedio ${\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\\\\fnMicrosoft {\\\\fnMicrosoft {\\fnMicrosoft {\\\\\\\\\fnMicrosoft {\\\\fnMicrosoft {\\\\fnMicrosoft}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fnMin {n}{2}p}$ bordes. La distribución del grado de cualquier vértice particular es binomial:

${\displaystyle P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k} }$

donde n es el número total de vértices en el gráfico. Dado que

${\displaystyle P(\deg(v)=k)\to {\frac {(np)}\mathrm {e} {-np}}\quad! {\text{ as }n\to \infty {\text{ and }np={\text{constant}}}}$

Esta distribución es de Poisson para n grande y np = constante.

En un artículo de 1960, Erdős y Rényi describieron el comportamiento de G(n, p) con mucha precisión para distintos valores de p. Sus resultados incluyeron lo siguiente:

• Si np # 1, luego un gráfico # G()n, p) casi seguramente no tendrá componentes conectados de tamaño mayor que O(log(n)).
• Si np = 1, luego un gráfico G()n, p) casi seguramente tendrá un componente más grande cuyo tamaño es de orden n^2/3.
• Si np → c Ø 1, donde c es una constante, luego un gráfico en G()n, p) casi seguramente tendrá un componente gigante único que contiene una fracción positiva de los vértices. Ningún otro componente contendrá más de O(log(n) vértices.
• Si ${\displaystyle p made{\tfrac {(1-\varepsilon)\ln No.$, entonces un gráfico en G()n, p) casi seguramente contener vertices aislados, y por lo tanto ser desconectado.
• Si ${\displaystyle p ## {\tfrac {(1+\varepsilon)\ln No.$, entonces un gráfico en G()n, p) casi seguramente estará conectado.

Así ${\fnMicroc {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\\fnMicrosoft {\\\\\fnMicrosoft {\fnMicrosoft {\\fn\\\\\\\fnMicrosoft {\\\fnMicrosoft {\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fn\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fn\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fnMin No.$ es un umbral agudo para la conexión de G()n, p).

Se pueden describir otras propiedades del grafo casi con precisión, ya que n tiende a infinito. Por ejemplo, existe una k(n) (aproximadamente igual a 2log₂(n)) tal que la camarilla más grande en G(n, 0,5) tiene casi con seguridad un tamaño de k(n) o de k(n) + 1.

Por lo tanto, aunque encontrar el tamaño de la camarilla más grande en un grafo es NP-completo, el tamaño de la camarilla más grande en un grafo "típico" (según este modelo) se entiende muy bien.

Los gráficos de doble arista de los gráficos de Erdos-Renyi son gráficos con una distribución de grados casi igual, pero con correlaciones de grados y un coeficiente de agrupamiento significativamente más alto.

En la teoría de la percolación se examina un grafo finito o infinito y se eliminan aristas (o enlaces) aleatoriamente. Por lo tanto, el proceso de Erdős–Rényi es, de hecho, una percolación de enlaces no ponderada en el grafo completo. (Se hace referencia a la percolación en la que se eliminan nodos y/o enlaces con pesos heterogéneos como percolación ponderada). Como la teoría de la percolación tiene muchas de sus raíces en la física, gran parte de la investigación realizada se centró en las redes en espacios euclidianos. La transición en np = 1 de componente gigante a componente pequeño tiene análogos para estos grafos, pero para las redes el punto de transición es difícil de determinar. Los físicos a menudo se refieren al estudio del grafo completo como una teoría de campo medio. Por lo tanto, el proceso de Erdős–Rényi es el caso de campo medio de la percolación.

También se realizó un trabajo significativo sobre la percolación en gráficos aleatorios. Desde el punto de vista de un físico esto todavía sería un modelo de campo medio, por lo que la justificación de la investigación se formula a menudo en términos de la robustez del gráfico, visto como una red de comunicación. Dado un gráfico aleatorio n ≫ 1 nodos con un grado promedio ${\displaystyle \langle k\rangle }$. Quitar aleatoriamente una fracción ${\displaystyle 1-p'}$ de los nodos y dejar sólo una fracción ${\displaystyle p'}$ de la red. Existe un umbral crítico de percolación ${\displaystyle p'_{c}={\tfrac {1}{\langle k\rangle}}}$ debajo del cual la red se fragmenta mientras arriba ${\displaystyle p'_{c}$ un componente gigante conectado del orden n existe. El tamaño relativo del componente gigante, P_JUEGO, se da por

${\displaystyle P_{\infty }=p'[1-\exp(-\langle k\rangle P_{\infty })].\,}$

Ambas de las dos hipótesis principales del modelo G(n, p) (que las aristas son independientes y que cada arista es igualmente probable) pueden ser inapropiadas para modelar ciertos fenómenos de la vida real. Los grafos de Erdős–Rényi tienen una baja agrupación, a diferencia de muchas redes sociales. Algunas alternativas de modelado incluyen el modelo de Barabási–Albert y el modelo de Watts y Strogatz. Estos modelos alternativos no son procesos de percolación, sino que representan un modelo de crecimiento y recableado, respectivamente. Otra familia alternativa de modelos de grafos aleatorios, capaces de reproducir muchos fenómenos de la vida real, son los modelos de grafos aleatorios exponenciales.

El modelo G(n, p) fue introducido por primera vez por Edgar Gilbert en un artículo de 1959 en el que estudiaba el umbral de conectividad mencionado anteriormente. El modelo G(n, M) fue introducido por Erdős y Rényi en su artículo de 1959. Al igual que Gilbert, sus primeras investigaciones se centraron en la conectividad de G(n, M), y el análisis más detallado se realizó en 1960.

Se obtuvo un límite continuo del gráfico cuando ${\displaystyle p}$ es de orden ${\displaystyle 1/n}$. Específicamente, considere la secuencia de gráficos ${\displaystyle G_{n}:=G(n,1/n+\lambda n^{-{\frac {4}{3}}}}}$ para ${\displaystyle \lambda \in \mathbb {R}$. El objeto límite se puede construir de la siguiente manera:

• Primero, generar una difusión ${\displaystyle W^{\lambda }(t):=W(t)+\lambda t-{\frac {\fnK}} {}}} {\c}} {\c}}}} {\c}}} {\c}}}}}} {\c}}}}}}} {\c}}}}}} {\c}}}}} {\c}}}} {}}}}}}}} {}}}}}}} {}}}}}}}}} {}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$ Donde ${\displaystyle W.$ es un movimiento normal de Brownian.
• De este proceso, definimos el proceso reflejado ${\displaystyle R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)}$. Este proceso se puede ver como que contiene muchas excursiones sucesivas (no una excursión Brownian bastante, ver). Porque la deriva ${\displaystyle W^{\lambda }$ está dominado por ${\displaystyle -{\frac {\fnK}} {}}} {\c}} {\c}}}} {\c}}} {\c}}}}}} {\c}}}}}}} {\c}}}}}} {\c}}}}} {\c}}}} {}}}}}}}} {}}}}}}} {}}}}}}}}} {}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$, estas excursiones se vuelven más cortas y más cortas ${\displaystyle t\to +\infty}$. En particular, se pueden clasificar en orden de reducción de longitudes: podemos dividir ${\displaystyle \mathbb {R}$ en intervalos ${\displaystyle (C_{i})_{i\in \mathbb {N}$ de la reducción de longitudes tal que ${\displaystyle R^{\lambda }$ restringidos a ${\displaystyle C_{i}$ es una excursión Brownian para cualquier ${\displaystyle i\in \mathbb {N}$.
• Ahora, considere una excursión ${\displaystyle (e(s))_{s\in [0,1]}$. Construir un gráfico aleatorio como sigue:

  

  • Construir un árbol real ${\displaystyle T_{e}$ (ver árbol Brownian).
  • Considere un proceso de punto Poisson ${\displaystyle \Xi}$ on ${\displaystyle [0,1]\times \mathbb {R} _{+}$ con intensidad de unidad. A cada punto ${\displaystyle (x,s)\in \Xi }$ tales que ${\displaystyle x\leq e(s)}$, corresponde a un nodo interno subyacente y una hoja del árbol ${\displaystyle T_{e}$. Identificando los dos vértices, el árbol ${\displaystyle T_{e}$ se convierte en un gráfico ${\displaystyle "Gamma"$

Aplicando este procedimiento, se obtiene una secuencia de gráficos infinitos aleatorios de tamaños decrecientes: ${\displaystyle (\Gamma _{i})_{i\in \mathbb {N}$. El teorema declara que este gráfico corresponde en cierto sentido al objeto límite ${\displaystyle G_{n}$ como ${\displaystyle n\to +\infty }$.

• Gráfico Rado – Gráfico infinito que contiene todos los gráficos contables, el gráfico formado por la extensión del G()n, p) modelo a gráficos con un número contablemente infinito de vértices. A diferencia del caso finito, el resultado de este proceso infinito es (con probabilidad 1) el mismo gráfico, hasta el isomorfismo.
• Evolución de doble fase – Proceso que impulsa la autoorganización dentro de sistemas complejos de adaptación describe formas en que las propiedades asociadas con el modelo Erdős–Rényi contribuyen a la aparición del orden en los sistemas.
• Modelos gráficos aleatorios exponenciales – modelos estadísticos para el análisis de redesPáginas que muestran descripciones de wikidata como retroceso describir una distribución general de probabilidad de gráficos en "n" nodos dado un conjunto de estadísticas de red y varios parámetros asociados con ellos.
• Modelo de bloque estocástico – Concepto en ciencia de red, una generalización del modelo Erdős–Rényi para gráficos con estructura comunitaria latente
• Modelo Watts–Strogatz – Método de generación de gráficos aleatorios del pequeño mundo
• Modelo Barabási–Albert – algoritmo de generación de red sin escala

• West, Douglas B. (2001). Introducción al Gráfico Teoría (2a edición). Prentice Hall. ISBN 0-13-014400-2.
• Newman, M. E. J. (2010). Networks: An Introduction. Oxford.

• Video: Gráfico aleatorio Erdos-Renyi