Modelo Erdős-Renyi

El modelo Erdős-Rényi es uno de los dos modelos de generación de gráficos aleatorios estrechamente relacionados . Los modelos llevan el nombre de los matemáticos Pal Erdős y Alfred Rényi , quienes introdujeron por primera vez uno de los modelos en 1959 [1] [2] , mientras que Edgar Hilbert propuso otro modelo de forma simultánea e independiente de Erdős y Rényi [3] . En el modelo de Erdős y Rényi, todos los gráficos con un conjunto fijo de vértices y un conjunto fijo de aristas son igualmente probables. En el modelo de Hilbert, cada borde tiene una probabilidad fija de presencia o ausencia independiente de otros bordes. Estos modelos se pueden utilizar en el método probabilísticopara probar la existencia de gráficos que satisfacen varias propiedades, o para proporcionar una definición precisa, se entiende que esta propiedad se cumple para casi todos los gráficos.

Definición

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

En el modelo , se elige un gráfico de manera uniforme y aleatoria del conjunto de todos los gráficos que tienen n vértices y M aristas. Por ejemplo, en el modelo, cada uno de los tres gráficos posibles con tres vértices y dos aristas se selecciona con una probabilidad de 1/3. ${\ estilo de visualización G (n, M)}$ ${\ estilo de visualización G (3,2)}$
En el modelo, se construye un gráfico agregando bordes al azar. Cada arista se incluye en el gráfico con probabilidad p , independientemente de las otras aristas. De manera equivalente, todos los gráficos con n nodos y M aristas tienen la misma probabilidad. ${\ estilo de visualización G (n, p)}$

p^{M}(1-p)^{{n \elegir 2}-M}.

El parámetro p en este modelo se puede considerar como una función del peso. A medida que p crece de 0 a 1, es más probable que el modelo incluya gráficos con más bordes. En particular, el caso p = 0.5 corresponde al caso en que todos los gráficos con n vértices serán elegidos con igual probabilidad.

{\ estilo de visualización 2 ^ {\ binom {n} {2}}}

El comportamiento de los gráficos aleatorios se estudia a menudo cuando n , el número de vértices del gráfico, tiende a infinito. Aunque p y M pueden ser fijos en este caso, también pueden depender de una función de n . Por ejemplo, la declaración

Casi todas las gráficas están conectadas.

{\ estilo de visualización G (n, 2ln (n)/n)}

medio

Como n tiende a infinito, la probabilidad de que un gráfico con n vértices y una probabilidad de inclusión de aristas 2ln( n )/ n sea conectado tiende a 1.

Comparación de los dos modelos

La expectativa matemática del número de aristas en es igual a , y por la ley de los grandes números, cualquier gráfico en B casi con seguridad tendrá aproximadamente este número de aristas. Por lo tanto, en términos generales, si , entonces G ( n , p ) debería comportarse como G ( n , M ) s a medida que n crece . ${\ estilo de visualización G (n, p)}$ ${\tbinom {n}{2}}p$ ${\ estilo de visualización G (n, p)}$ $pn^{2}\a\infty$ $M={\tbinom{n}{2}}p$

Este es el caso de muchas propiedades gráficas. Si P es cualquier propiedad de un 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 in " y " P vale para casi todos los gráficos en " son equivalentes (para ). Por ejemplo, esto se cumple si P tiene la propiedad de ser conexo, o si P tiene la propiedad de tener un ciclo hamiltoniano . Sin embargo, esto no se cumple necesariamente para las propiedades no monótonas (por ejemplo, la propiedad de tener un número par de aristas). ${\ estilo de visualización G (n, p)}$ $G(n,{\tbinom {n}{2}}p)$ $pn^{2}\a\infty$

En la práctica, el modelo es uno de los más utilizados en la actualidad, en parte por la facilidad de análisis que ofrece la independencia de los bordes. ${\ estilo de visualización G (n, p)}$

Propiedades del gráfico ${\ estilo de visualización G (n, p)}$

Con la notación anterior, el gráfico tiene, en promedio, aristas. La distribución de grados de vértice es binomial [4] : ${\ estilo de visualización G (n, p)}$ ${\tbinom {n}{2}}p$

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. Porque el

P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!)}}

en y

n\to\infty

np={\text{constante)),

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

En un artículo de 1960, Erdős y Rényi [5] describieron el comportamiento con mucha precisión para varios valores de p . Sus resultados incluyen: ${\ estilo de visualización G (n, p)}$

Si np < 1, es casi seguro que el gráfico no tendrá componentes conectados de tamaño mayor que O(log( n )). ${\ estilo de visualización G (n, p)}$
Si np = 1, entonces el gráfico en tendrá componentes grandes, cuyo tamaño es del orden de n 2/3 . ${\ estilo de visualización G (n, p)}$
Si , donde c es una constante, es casi seguro que el gráfico en tendrá un solo componente gigante que contiene una proporción positiva de vértices. Ningún otro componente tendrá más de O(log( n )) vértices. $np\to c>1$ ${\ estilo de visualización G (n, p)}$
Si , entonces el gráfico en casi con seguridad contendrá vértices aislados y, por lo tanto, estará desconectado. $p<{\tfrac {(1-\varepsilon)\lnn}{n))$ ${\ estilo de visualización G (n, p)}$
Si , es casi seguro que la gráfica de in será conexa. $p>{\tfrac {(1+\varepsilon)\lnn}{n))$ ${\ estilo de visualización G (n, p)}$

Por lo tanto, es el umbral de probabilidad exacto para la conectividad . ${\tfrac {\lnn}{n))$ ${\ estilo de visualización G (n, p)}$

Otras propiedades del gráfico se pueden describir casi exactamente como n tiende a infinito. Por ejemplo, hay k ( n ) (aproximadamente igual a 2log 2 ( n )), de modo que la camarilla más grande es casi con seguridad de tamaño k ( n ) o [6] . ${\ estilo de visualización G (n, 0, 5)}$ ${\ estilo de visualización k (n) + 1}$

Entonces, aunque el problema de 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 bien.

Los gráficos de borde dual de los gráficos de Erdős-Rényi son gráficos con casi las mismas distribuciones de grados, pero con una correlación de grados y un coeficiente de agrupamiento mucho más alto [7] .

Relación con la percolación

En la teoría de la percolación , se examina un gráfico finito o infinito y los bordes (o conexiones) se eliminan aleatoriamente. Entonces, el proceso de Erdős-Rényi es, de hecho, una percolación no ponderada en el gráfico completo . Dado que la teoría de la percolación tiene profundas raíces en la física , se ha realizado una gran cantidad de investigación sobre redes en 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 hablan de estudiar el gráfico completo como un método de campo autoconsistente . Entonces el proceso de Erdős-Rényi es el caso de un campo de percolación promedio.

También se ha realizado un trabajo significativo sobre la filtración en gráficos aleatorios. Desde un punto de vista físico, el modelo sigue siendo un modelo de campo medio, por lo que la motivación para la investigación a menudo se formula en términos de la estabilidad de un gráfico visto como una red de comunicación. Sea un grafo aleatorio con nodos de grado medio < k >. Quitamos el recurso compartido de nodos y dejamos el recurso compartido p′ de la red. Hay un umbral de percolación crítico , por debajo del cual la red se fragmenta, mientras que por encima del umbral hay un componente conectado gigante de orden n . El tamaño relativo del componente gigante viene dado por la fórmula [5] [1] [2] [8] . ${\ estilo de visualización n \ gg 1}$ ${\ estilo de visualización 1-p'}$ $p'_{c}={\tfrac {1}{\langle k\rangle ))$ ${\ Displaystyle p'_ {c}}$ ${\ Displaystyle P_ {\ infinito}}$

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

Advertencias

Los principales supuestos de ambos modelos (que los bordes son independientes y que cada borde tiene la misma probabilidad) pueden no ser adecuados para modelar algunos fenómenos de la vida real. En particular, la distribución de grados de vértices de los gráficos de Erdős-Rényi no tiene colas pesadas de la distribución, mientras que se considera que la distribución tiene una cola pesada en muchas redes reales . Además, los gráficos de Erdős-Rényi tienen un agrupamiento bajo, lo que no ocurre en muchas redes sociales. Para ver alternativas de modelos populares, consulte los artículos The Barabasi-Albert Model y The Watts and Strogats Model . Estos modelos alternativos no son procesos de percolación , sino modelos de crecimiento y recableado, respectivamente. El modelo de interacción de la red Erdős-Rényi fue desarrollado recientemente por Buldyrev et al .[9] . ${\ estilo de visualización G (n, p)}$

Historia

El modelo fue propuesto por primera vez por Edgar Hilbert en un artículo de 1959 que estudiaba el umbral de conectividad mencionado anteriormente [3] . El modelo fue propuesto por Erdős y Renyi en su artículo de 1959. Como en el caso de Hilbert, investigaron la conectividad , y en 1960 se realizó un análisis más detallado. ${\ estilo de visualización G (n, p)}$ ${\ estilo de visualización G (n, M)}$ ${\ estilo de visualización G (n, M)}$

Variaciones y generalizaciones

Un grafón (teoría de grafos) es un modelo más general de un grafo aleatorio.

El gráfico de Rado , formado al extender el modelo a gráficos con un número contable de vértices. A diferencia del caso final, el resultado de este proceso infinito es (con probabilidad 1 ) la misma gráfica salvo isomorfismo. ${\ estilo de visualización G (n, p)}$

Modelo Barabashi-Albert .

Notas

↑ 1 2 Erdős, Rényi, 1959 , p. 290–297.
↑ 12 Bollobas , 2001 .
↑ 1 2 Gilbert, 1959 , pág. 1141–1144.
↑ Newman, Strogatz, Watts, 2001 , pág. 026118.
↑ 1 2 ( Erdős, Rényi 1960 , 17–61) La probabilidad p utilizada aquí se refiere a $N(n)={\tbinom {n}{2}}p$
↑ Matula, 1972 , pág. A-382.
↑ Ramezanpour, Karimipour, Mashaghi, 2003 , pág. 046107.
↑ Bollobás, Erdős, 1976 , p. 419–427.
↑ Buldyrev, Parshani, Paul, Stanley, Havlin, 2010 , pág. 1025–8.

Literatura

Mark EJ Newman, Strogatz SH, Watts DJ Gráficos aleatorios con distribuciones de grados arbitrarios y sus aplicaciones // Physical Review E. - 2001. - T. 64 . -doi : 10.1103/ PhysRevE.64.026118 . - . -arXiv : cond - mat/0007235 . , Ecu. (una)
Erdős P., Rényi A. Sobre la evolución de grafos aleatorios // Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publicaciones del Instituto de Matemáticas de la Academia Húngara de Ciencias]. - 1960. - T. 5 .
David W. Matula. El problema del partido de los empleados // Avisos de la American Mathematical Society. - 1972. - febrero ( vol. 19 ). - SA-382 .
Ramezanpour A., Karimipour V., Mashaghi A. Generación de redes correlacionadas a partir de redes no correlacionadas // Physical Review E. - 2003. - Abril ( vol. 67 , número 4 ). -doi : 10.1103/ PhysRevE.67.046107 . - . -arXiv : cond - mat/0212469 .
Erdős P., Renyi A. Sobre gráficos aleatorios. I // Publicaciones Mathematicae. - 1959. - T. 6 .
Bollobas B. Gráficos aleatorios. — 2do. - 2001. - ISBN 0-521-79722-5 .
Bollobás B., Erdős P. Cliques en gráficos aleatorios // Procedimientos matemáticos de la Sociedad Filosófica de Cambridge. - 1976. - T. 80 , núm. 3 . -doi : 10.1017/ S0305004100053056 . - .
Buldyrev SV, Parshani R., Paul G., Stanley HE, Havlin S. Cascada catastrófica de fallas en redes interdependientes // Naturaleza. - 2010. - T. 464 , núm. 7291 . -doi : 10.1038/ naturaleza08932 . - . -arXiv : 0907.1182 . _ — PMID 20393559 .
Gilbert ES Gráficos aleatorios // Anales de estadística matemática. - 1959. - T. 30 , núm. 4 . -doi : 10.1214 / aoms/1177706098 .

Lectura para leer más

Raigorodsky, Andrei Mijailovich Modelos de grafos aleatorios . - M. : MTSNMO, 2011. - ISBN 978-5-94057-840-6 .
Douglas B. Oeste. Introducción a la Teoría de Grafos. - 2001. - ISBN 0-13-014400-2 .
Redes Newman MEJ : una introducción. — 2010.
Redes Complejas: Estructura, Robustez y Función . — 2010.