Modelo Erdos-Renyi

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En el campo matemático de la teoría de grafos, el modelo Erdős-Rényi es uno de dos modelos estrechamente relacionados para generar gráficos aleatorios o la evolución de una red aleatoria. Llevan el nombre de los matemáticos húngaros Paul Erdős y Alfréd Rényi, quienes introdujeron por primera vez uno de los modelos en 1959, mientras que Edgar Gilbert introdujo el otro modelo al mismo tiempo e independientemente de Erdős y Rényi. En el modelo de Erdős y Rényi, todos los gráficos en un conjunto de vértices fijos con un número fijo de aristas son igualmente probables; en el modelo introducido por Gilbert, también llamado modelo Erdős-Rényi-Gilbert,cada borde tiene una probabilidad fija de estar presente o ausente, independientemente de los otros bordes. Estos modelos se pueden usar en el método probabilístico para probar la existencia de gráficos que satisfacen varias propiedades, o para proporcionar una definición rigurosa de lo que significa que una propiedad se cumpla para casi todos los gráficos.

Definición

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

En el ${ estilo de visualización G (n, M)}$ modelo, se elige un gráfico uniformemente al azar de la colección de todos los gráficos que tienen $norte$ nodos y $METRO$ aristas. Se considera que los nodos están etiquetados, lo que significa que los gráficos obtenidos entre sí mediante la permutación de los vértices se consideran distintos. Por ejemplo, en el ${ estilo de visualización G (3,2)}$ modelo, hay tres gráficos de dos aristas en tres vértices etiquetados (uno para cada elección del vértice central en una ruta de dos aristas), y cada uno de estos tres gráficos se incluye con probabilidad ${tfrac{1}{3}}$ .
En el $G(n,p)$ modelo, se construye un gráfico conectando nodos etiquetados al azar. Cada arista se incluye en el gráfico con probabilidad $pags$ , independientemente de cualquier otra arista. De manera equivalente, la probabilidad de generar cada gráfico que tiene $norte$ nodos y $METRO$ aristas es ${displaystyle p^{M}(1-p)^{{n elegir 2}-M}.}$ El parámetro $pags$ en este modelo se puede considerar como una función de ponderación; a medida que $pags$ aumenta de ${ estilo de visualización 0}$ a $1$ , es cada vez más probable que el modelo incluya gráficos con más bordes y cada vez menos probable que incluya gráficos con menos bordes. En particular, el caso $p={tfrac{1}{2}}$ corresponde al caso donde todos los $2^algunos{n}{2}$ gráficos en los $norte$ vértices se eligen con la misma probabilidad.

El comportamiento de grafos aleatorios suele estudiarse en el caso en que $norte$ , el número de vértices, tiende a infinito. Aunque $pags$ y $METRO$ pueden ser fijos en este caso, también pueden ser funciones dependiendo de $norte$ . Por ejemplo, la afirmación de que casi todos los gráficos en ${ estilo de visualización G (n, 2 ln (n) / n)}$ están conectados significa que, como $norte$ tiende a infinito, la probabilidad de que un gráfico en los $norte$ vértices con probabilidad de borde ${ estilo de visualización 2 ln (n) / n}$ sea conectado tiende a $1$ .

Comparación entre los dos modelos

El número esperado de aristas en G (n, p) es $tbinom{n}{2}p$ , y por la ley de los grandes números cualquier gráfico en G (n, p) casi seguramente tendrá aproximadamente esta cantidad de aristas (siempre que la cantidad esperada de aristas tienda a infinito). Por lo tanto, una heurística aproximada es que si pn → ∞, entonces G (n, p) debería comportarse de manera similar a G (n, M) a $M=tbinom{n}{2} p$ medida que n aumenta.

Para muchas propiedades gráficas, este es el caso. Si P es cualquier propiedad del gráfico que es monótona con respecto al orden del subgráfico (lo que significa que si A es un subgráfico de B y A satisface P, entonces B también satisfará P), entonces las afirmaciones " P se cumplen para casi todos los gráficos en G (n, p)" y " P se cumple para casi todos los gráficos en $G(n, tbinom{n}{2} p)$ " son equivalentes (siempre que pn → ∞). Por ejemplo, esto se cumple si P es la propiedad de ser conexo, o si Pes la propiedad de contener un ciclo hamiltoniano. Sin embargo, esto no se cumple necesariamente para las propiedades no monótonas (p. ej., la propiedad de tener un número par de aristas).

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

Propiedades de G (n, p)

Con la notación anterior, un gráfico en G (n, p $tbinom{n}{2} pags$ ) tiene aristas en promedio. La distribución del grado de cualquier vértice en particular es binomial: ${displaystyle P(deg(v)=k)={n-1 elegir k}p^{k}(1-p)^{n-1-k},}$

donde n es el número total de vértices en el gráfico. Ya que ${displaystyle P(deg(v)=k)to {frac {(np)^{k}mathrm {e} ^{-np}}{k!}}quad {text{ as } }nto infty {text{ y }}np={text{constante}},}$

esta distribución es Poisson para n grande y np = const.

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

Si np < 1, entonces un gráfico en G (n, p) casi seguramente no tendrá componentes conectados de tamaño mayor que O(log(n)).
Si np = 1, entonces un gráfico en G (n, p) casi seguramente tendrá un componente más grande cuyo tamaño es de orden n.
Si np → c > 1, donde c es una constante, entonces un gráfico en G (n, p) casi seguramente tendrá un único componente gigante 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<{tfrac {(1-varepsilon)ln n}{n}}}$ , entonces un gráfico en G (n, p) casi seguramente contendrá vértices aislados y, por lo tanto, será desconectado.
Si ${displaystyle p>{tfrac {(1+varepsilon)ln n}{n}}}$ , entonces un gráfico en G (n, p) casi seguramente será conexo.

Por lo tanto ${displaystyle {tfrac {lnn}{n}}}$ , es un umbral definido para la conectividad de G (n, p).

Otras propiedades del gráfico se pueden describir casi con precisión cuando n tiende a infinito. Por ejemplo, hay un k (n) (aproximadamente igual a 2log ₂ (n)) tal que la camarilla más grande en G (n, 0.5) tiene casi seguramente el tamaño de k (n) o k (n) + 1.

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

Los gráficos de bordes duales de los gráficos Erdos-Renyi son gráficos con casi la misma distribución de grados, pero con correlaciones de grados y un coeficiente de agrupamiento significativamente más alto.

Relación con la percolación

En la teoría de la percolación, uno examina un gráfico finito o infinito y elimina los bordes (o enlaces) al azar. Por lo tanto, el proceso de Erdős-Rényi es, de hecho, una filtración de enlaces no ponderada en el gráfico completo. (Uno se refiere a la percolación en la que se eliminan nodos y/o enlaces con pesos heterogéneos como percolación ponderada). Dado que la teoría de la filtración tiene gran parte de sus raíces en la física, gran parte de la investigación realizada se centró en las redes de los espacios euclidianos. La transición en np = 1 del componente gigante al componente pequeño tiene análogos para estos gráficos, pero para los retículos el punto de transición es difícil de determinar. Los físicos a menudo se refieren al estudio del gráfico completo como una teoría del campo medio. Por lo tanto, el proceso de Erdős-Rényi es el caso de percolación de campo medio.

También se realizó un trabajo significativo sobre la filtración en gráficos aleatorios. Desde el punto de vista de un físico, esto seguiría siendo un modelo de campo medio, por lo que la justificación de la investigación a menudo se formula en términos de la solidez del gráfico, visto como una red de comunicación. Dado un gráfico aleatorio de n ≫ 1 nodos con un grado medio ${ estilo de visualización langle k rangle}$ . Elimine aleatoriamente una fracción ${ estilo de visualización 1-p'}$ de nodos y deje solo una fracción $pags'$ de la red. Existe un umbral crítico de percolación $p'_c=tfrac{1}{langle krangle}$ por debajo del cual la red se fragmenta mientras que por encima existe un $ordenador personal$ componente conectado gigante de orden n. El tamaño relativo del componente gigante, P _∞, viene dado por $P_infty= p'[1-exp(-langle k rangle P_infty)]. ,$

Advertencias

Los dos supuestos principales del modelo G (n, p) (que los bordes son independientes y que cada borde es igualmente probable) pueden ser inapropiados para modelar ciertos fenómenos de la vida real. Los gráficos de Erdős-Rényi tienen un agrupamiento bajo, 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 filtración, sino que representan un modelo de crecimiento y recableado, respectivamente.

Historia

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

Contenido relacionado

Más resultados...