Modelo Erdős-Rényi

Dos modelos estrechamente relacionados para generar gráficos aleatorios.

Un gráfico de Erdős-Rényi-Gilbert con 1000 vértices en la probabilidad del borde crítico , que muestra un componente grande y muchos pequeños ${\displaystyle p=1/(n-1)}$

En el campo matemático de la teoría de grafos , el modelo Erdős-Rényi se refiere a uno de dos modelos estrechamente relacionados para generar gráficos aleatorios o la evolución de una red aleatoria . Estos modelos llevan el nombre de los matemáticos húngaros Paul Erdős y Alfréd Rényi , quienes introdujeron uno de los modelos en 1959. ^{[1] [2]} Edgar Gilbert introdujo el otro modelo simultáneamente e independientemente de Erdős y Rényi. ^[3] 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 , ^[4] 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 gráficos que satisfacen diversas 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.

Un gráfico generado por el modelo binomial de Erdős y Rényi ( p  = 0,01)

• En el modelo, se elige un gráfico uniformemente al azar de la colección de todos los gráficos que tienen nodos y aristas. Los nodos se consideran etiquetados, lo que significa que los gráficos obtenidos entre sí permutando los vértices se consideran distintos. Por ejemplo, en el modelo, hay tres gráficos de dos aristas en tres vértices etiquetados (uno para cada elección del vértice medio en un camino de dos aristas), y cada uno de estos tres gráficos se incluye con probabilidad . ${\displaystyle G(n,M)}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle G(3,2)}$ ${\displaystyle {\tfrac {1}{3}}}$
• En el modelo, se construye un gráfico conectando nodos etiquetados al azar. Cada arista se incluye en el gráfico con probabilidad , independientemente de todas las demás aristas. De manera equivalente, la probabilidad de generar cada gráfico que tenga nodos y aristas es ${\displaystyle G(n,p)}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle M}$
  $${\displaystyle p^{M}(1-p)^{{n \choose 2}-M}.}$$
  El parámetro de este modelo puede considerarse como una función de ponderación; a medida que aumenta de a , es cada vez más probable que el modelo incluya gráficos con más aristas y cada vez menos probable que incluya gráficos con menos aristas. En particular, el caso corresponde al caso en el que todos los gráficos sobre vértices se eligen con la misma probabilidad. ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle p={\tfrac {1}{2}}}$ ${\displaystyle 2^{\binom {n}{2}}}$ ${\displaystyle n}$

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

Comparación entre los dos modelos.

El número esperado de aristas en G ( n , p ) es , y según la ley de los números grandes, cualquier gráfico en G ( n , p ) casi seguramente tendrá aproximadamente esta cantidad de aristas (siempre que el número esperado 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 medida que n aumenta. ${\displaystyle {\tbinom {n}{2}}p}$ ${\displaystyle M={\tbinom {n}{2}}p}$

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

En la práctica, el modelo G ( n , p ) es el más utilizado hoy en día, 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 ) tiene en promedio aristas. La distribución del grado de cualquier vértice particular es binomial : ^[5] ${\displaystyle {\tbinom {n}{2}}p}$

${\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 del gráfico. Desde

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

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

En un artículo de 1960, Erdős y Rényi ^[6] 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 sea de orden n ^2/3 .
• Si np → c  > 1, donde c es una constante, entonces un gráfico en G ( n ,  p ) casi seguramente tendrá un componente gigante único que contenga una fracción positiva de los vértices. Ningún otro componente contendrá más de O(log( n )) vértices.
• Si , entonces un gráfico en G ( n , p ) casi seguramente contendrá vértices aislados y, por lo tanto, estará desconectado. ${\displaystyle p<{\tfrac {(1-\varepsilon )\ln n}{n}}}$
• Si , entonces es casi seguro que una gráfica en G ( n , p ) será conexa. ${\displaystyle p>{\tfrac {(1+\varepsilon )\ln n}{n}}}$

Por tanto, existe un umbral estricto para la conectividad de G ( n , p ). ${\displaystyle {\tfrac {\ln n}{n}}}$

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 con seguridad tamaño k ( n ) o k ( n ) + 1. ^{[ 7]}

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 comprende muy bien.

Los gráficos de borde dual de los gráficos de Erdos-Renyi son gráficos con casi la misma distribución de grados, pero con correlaciones de grados y un coeficiente de agrupamiento significativamente mayor . ^[8]

Relación con la percolación

En la teoría de la percolación, se examina un gráfico finito o infinito y se eliminan los bordes (o enlaces) al azar. Por tanto, el proceso Erdős-Rényi es de hecho una filtración de enlaces no ponderados en el gráfico completo . (Uno se refiere a la percolación en la que los nodos y/o enlaces se eliminan con pesos heterogéneos como percolación ponderada). Como la teoría de la percolación tiene muchas 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 de componente gigante a componente pequeño tiene analogías para estos gráficos, pero para las redes 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 de campo medio . Por tanto, el proceso Erdős-Rényi es el caso de percolación de campo medio.

También se realizaron algunos trabajos importantes 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 promedio  . Elimine aleatoriamente una fracción de nodos y deje solo una fracción de la red. Existe un umbral de percolación crítico por debajo del cual la red se fragmenta, mientras que por encima existe un componente conectado gigante de orden n . El tamaño relativo del componente gigante, P _∞ , viene dado por ^{[6] [1] [2] [9]} ${\displaystyle \langle k\rangle }$ ${\displaystyle 1-p'}$ ${\displaystyle p'}$ ${\displaystyle p'_{c}={\tfrac {1}{\langle k\rangle }}}$ ${\displaystyle p'_{c}}$

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

Advertencias

Los dos supuestos principales del modelo G ( n , p ) (que las aristas son independientes y que cada arista es igualmente probable) pueden ser inapropiados para modelar ciertos fenómenos de la vida real. Los gráficos Erdős-Rényi tienen una agrupación baja, a diferencia de muchas redes sociales. ^[10] 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 gráficos aleatorios, capaces de reproducir muchos fenómenos de la vida real, son los modelos de gráficos aleatorios exponenciales .

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. ^[3] 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 en 1960 se realizó un análisis más detallado.

Representación de límite continuo de G crítico ( n , p )

El movimiento browniano con deriva cuadrática negativa se descompone en excursiones brownianas de tamaños decrecientes.

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

• Primero, generar una difusión donde sea un movimiento browniano estándar . ${\displaystyle W^{\lambda }(t):=W(t)+\lambda t-{\frac {t^{2}}{2}}}$ ${\displaystyle W}$
• A partir de este proceso definimos el proceso reflejado . Se puede considerar que este proceso contiene muchas excursiones sucesivas (no del todo una excursión browniana, ver ^[12] ). Debido a que la deriva de está dominada por , estas excursiones se vuelven cada vez más cortas a medida que . En particular, se pueden ordenar en orden de longitudes decrecientes: podemos dividirlos en intervalos de longitudes decrecientes de modo que se limite a una excursión browniana para cualquiera . ${\displaystyle R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)}$ ${\displaystyle W^{\lambda }}$ ${\displaystyle -{\frac {t^{2}}{2}}}$ ${\displaystyle t\to +\infty }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle (C_{i})_{i\in \mathbb {N} }}$ ${\displaystyle R^{\lambda }}$ ${\displaystyle C_{i}}$ ${\displaystyle i\in \mathbb {N} }$
• Ahora, considere una excursión . Construya una gráfica aleatoria de la siguiente manera: ${\displaystyle (e(s))_{s\in [0,1]}}$

  

  Una excursión browniana . Aquí el proceso tiene un único punto, marcado con un punto rojo. La línea roja corresponde a un único nodo interno del árbol asociado , la línea verde corresponde a una hoja de . Si se agrega una arista entre los dos nodos, se obtiene un gráfico con un solo ciclo. ${\displaystyle (e(t))_{t\in [0,1]}}$ ${\displaystyle \Xi }$ ${\displaystyle T_{e}}$ ${\displaystyle T_{e}}$

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

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

Ver también

• Gráfico de Rado  : gráfico infinito que contiene todos los gráficos contables, el gráfico formado al extender el modelo G ( n ,  p ) a gráficos con un número infinitamente contable 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  : el proceso que impulsa la autoorganización dentro de sistemas adaptativos complejos describe formas en que las propiedades asociadas con el modelo Erdős-Rényi contribuyen al surgimiento del orden en los sistemas.
• Modelos de gráficos aleatorios exponenciales  : los modelos estadísticos para análisis de redes Pages displaying wikidata descriptions as a fallbackdescriben una distribución de probabilidad general de gráficos en "n" nodos dado un conjunto de estadísticas de red y varios parámetros asociados con ellas.
• Modelo de bloques estocásticos , una generalización del modelo Erdős-Rényi para gráficos con estructura comunitaria latente
• Modelo Watts-Strogatz  : método para generar gráficos aleatorios de mundos pequeños
• Modelo Barabási-Albert  : algoritmo de generación de redes sin escala

Referencias

1. Erdős, P.; Rényi, A. (1959). "Sobre gráficos aleatorios. I" (PDF) . Publicaciones Mathematicae . 6 (3–4): 290–297. doi :10.5486/PMD.1959.6.3-4.12. S2CID  253789267. Archivado (PDF) desde el original el 7 de agosto de 2020 . Consultado el 23 de febrero de 2011 .
2. Bollobás, B. (2001). Gráficos aleatorios (2ª ed.). Prensa de la Universidad de Cambridge. ISBN 0-521-79722-5.
3. Gilbert, EN (1959). "Gráficos aleatorios". Anales de estadística matemática . 30 (4): 1141-1144. doi : 10.1214/aoms/1177706098 .
4. Fienberg, Stephen E. (2012). "Una breve historia de los modelos estadísticos para análisis de redes y desafíos abiertos". Revista de Estadística Computacional y Gráfica . 21 (4): 825–839. doi :10.1080/10618600.2012.738106. SEÑOR  3005799. S2CID  52232135.
5. Newman, marca. EJ; Strogatz, SH; Watts, DJ (2001). "Gráficos aleatorios con distribuciones de grados arbitrarios y sus aplicaciones". Revisión física E. 64 (2): 026118. arXiv : cond-mat/0007235 . Código bibliográfico : 2001PhRvE..64b6118N. doi : 10.1103/PhysRevE.64.026118. PMID  11497662. S2CID  360112., Ec. (1)
6. Erdős, P.; Rényi, A. (1960). "Sobre la evolución de los gráficos aleatorios" (PDF) . Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publicaciones del Instituto de Matemáticas de la Academia de Ciencias de Hungría] . 5 : 17–61. Archivado (PDF) desde el original el 1 de febrero de 2021 . Consultado el 18 de noviembre de 2011 .La probabilidad p utilizada aquí se refiere a ${\displaystyle N(n)={\tbinom {n}{2}}p}$
7. Matula, David W. (febrero de 1972). "El problema del partido de los empleados". Avisos de la Sociedad Matemática Estadounidense . 19 : A-382.
8. Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (abril de 2003). "Generación de redes correlacionadas a partir de redes no correlacionadas". Revisión física E. 67 (4): 046107. arXiv : cond-mat/0212469 . Código bibliográfico : 2003PhRvE..67d6107R. doi : 10.1103/PhysRevE.67.046107. PMID  12786436. S2CID  33054818.
9. Bollobás, B.; Erdős, P. (1976). "Cliques en gráficos aleatorios". Actas matemáticas de la Sociedad Filosófica de Cambridge . 80 (3): 419–427. Código Bib : 1976MPCPS..80..419B. doi :10.1017/S0305004100053056. S2CID  16619643.
10. Saberi, Abbas Ali (marzo de 2015). "Avances recientes en la teoría de la percolación y sus aplicaciones". Informes de Física . 578 : 12. arXiv : 1504.02898 . Código Bib : 2015PhR...578....1S. doi :10.1016/j.physrep.2015.03.003. S2CID  119209128 . Consultado el 30 de enero de 2022 .
11. Addario-Berry, L.; Broutin, N.; Goldschmidt, C. (1 de abril de 2012). "El límite continuo de gráficos aleatorios críticos". Teoría de la probabilidad y campos relacionados . 152 (3): 367–406. doi : 10.1007/s00440-010-0325-4 . ISSN  1432-2064. S2CID  253980763.
12. Aldous, David (1 de abril de 1997). "Excursiones brownianas, gráficos aleatorios críticos y el coalescente multiplicativo". Los anales de la probabilidad . 25 (2). doi : 10.1214/aop/1024404421 . ISSN  0091-1798. S2CID  16578106.

Literatura

• Oeste, Douglas B. (2001). Introducción a la teoría de grafos (2ª ed.). Prentice Hall. ISBN 0-13-014400-2.
• Newman, MEJ (2010). Redes: una introducción . Oxford.

enlaces externos

• Vídeo: Gráfico aleatorio de Erdos-Renyi