Modelo de 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 el borde crítico de probabilidad , 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 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. ^{[1] [2]} Edgar Gilbert introdujo el otro modelo contemporáneamente con e independientemente de Erdős y Rényi. ^[3] 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 son igualmente probables. En el modelo introducido por Gilbert, también llamado modelo de 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 grafos que satisfacen varias propiedades, o para proporcionar una definición rigurosa de lo que significa que una propiedad se cumpla para casi todos los grafos.

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 grafo de manera uniforme y aleatoria de la colección de todos los grafos que tienen nodos y aristas. Se considera que los nodos están etiquetados, lo que significa que los grafos obtenidos entre sí mediante la permutación de los vértices se consideran distintos. Por ejemplo, en el modelo, hay tres grafos 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 grafos 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 grafo conectando nodos etiquetados aleatoriamente. Cada arista se incluye en el grafo con probabilidad , independientemente de cada otra arista. Equivalentemente, la probabilidad de generar cada grafo que tiene nodos y aristas es El parámetro en este modelo puede considerarse como una función de ponderación; a medida que aumenta de a , el modelo se vuelve cada vez más probable que incluya grafos con más aristas y cada vez menos probable que incluya grafos con menos aristas. En particular, el caso corresponde al caso en el que todos los grafos en vértices se eligen con la misma probabilidad. ${\displaystyle G(n,p)}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle M}$ $${\displaystyle p^{M}(1-p)^{{n \choose 2}-M}.}$$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle p={\tfrac {1}{2}}}$ ${\displaystyle 2^{\binom {n}{2}}}$ ${\displaystyle n}$

El comportamiento de los grafos aleatorios se estudia a menudo en el caso en que , el número de vértices, tiende a infinito. Aunque y pueden ser fijos en este caso, también pueden ser funciones que dependen de . Por ejemplo, la afirmación de que casi todos los grafos en son conexos significa que, como tiende a infinito, la probabilidad de que un grafo en vértices con probabilidad de arista sea conexo 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 por la ley de los grandes números cualquier grafo 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 ) con a medida que n aumenta. ${\displaystyle {\tbinom {n}{2}}p}$ ${\displaystyle M={\tbinom {n}{2}}p}$

Para muchas propiedades de grafos, este es el caso. Si P es cualquier propiedad de grafo que es monótona con respecto al ordenamiento de 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 se cumple para casi todos los grafos en G ( n ,  p )" y " P se cumple para casi todos los grafos en " son equivalentes (siempre que pn ² → ∞). Por ejemplo, esto se cumple si P es la propiedad de estar conexo , o si P es la propiedad de contener un ciclo hamiltoniano . Sin embargo, esto no se cumplirá necesariamente 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 deGRAMO(norte,pag)

Con la notación anterior, un grafo 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 en el gráfico. Dado que

${\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 lo siguiente:

• Si np < 1, entonces un gráfico en G ( n ,  p ) casi seguramente no tendrá componentes conexos 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 del orden n ^2/3 .
• Si np → c  > 1, donde c es una constante, entonces un grafo en G ( n ,  p ) casi seguramente tendrá un único componente gigante 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 un gráfico en G ( n , p ) casi seguramente estará conexo. ${\displaystyle p>{\tfrac {(1+\varepsilon )\ln n}{n}}}$

Por lo tanto, existe un umbral claro 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 un 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 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 arista 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 más alto . ^[8]

Relación con la percolación

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 ha realizado un trabajo importante sobre la percolación en grafos 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 robustez del grafo, visto como una red de comunicación. Dado un grafo aleatorio de n  ≫ 1 nodos con un grado medio  . Retire aleatoriamente una fracción de nodos y deje solo una fracción de la red. Existe un umbral crítico de percolación por debajo del cual la red se fragmenta mientras que por encima existe un componente gigante conectado 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

Ambos 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. ^[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 con Gilbert, sus primeras investigaciones fueron sobre la conectividad de G ( n ,  M ), y el análisis más detallado se realizó en 1960.

Representación del límite continuo de la críticaGRAMO(norte,pag)

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

Se obtuvo un límite continuo del grafo cuando es de orden . ^[11] Específicamente, considere la secuencia de grafos 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, genere una difusión donde es 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 . Este proceso puede verse como que contiene muchas excursiones sucesivas (no exactamente una excursión browniana, véase ^[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 dividir en intervalos de longitudes decrecientes tales que restringido a es una excursión browniana para cualquier . ${\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 un gráfico aleatorio como sigue: ${\displaystyle (e(s))_{s\in [0,1]}}$

  

  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 añade una arista entre los dos nodos, se obtiene un grafo con un único ciclo. ${\displaystyle (e(t))_{t\in [0,1]}}$ ${\displaystyle \Xi }$ ${\displaystyle T_{e}}$ ${\displaystyle T_{e}}$

  • Construya un árbol real (ver árbol browniano ). ${\displaystyle T_{e}}$
  • Consideremos un proceso puntual de Poisson en con intensidad unitaria. A cada punto tal que , le corresponde un nodo interno subyacente y una hoja del árbol . Al identificar los dos vértices, el árbol se convierte en un grafo ${\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 grafos aleatorios infinitos de tamaño decreciente: . El teorema ^[11] establece que este grafo corresponde en cierto sentido al objeto límite de como . ${\displaystyle (\Gamma _{i})_{i\in \mathbb {N} }}$ ${\displaystyle G_{n}}$ ${\displaystyle n\to +\infty }$

Véase también

• Grafo de Rado  – Grafo infinito que contiene todos los grafos numerables, el grafo formado al extender el modelo G ( n ,  p ) a grafos con un número infinito numerable de vértices. A diferencia del caso finito, el resultado de este proceso infinito es (con probabilidad 1 ) el mismo grafo, salvo isomorfismo.
• Evolución de doble fase  : proceso que impulsa la autoorganización dentro de sistemas adaptativos complejos describe las 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 el 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 ellos.
• Modelo de bloques estocásticos , una generalización del modelo de Erdős–Rényi para gráficos con estructura de comunidad latente
• Modelo de Watts-Strogatz  : método para generar gráficos aleatorios de mundo pequeño
• 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). Grafos aleatorios (2.ª ed.). Cambridge University Press. 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 el 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. MR  3005799. S2CID  52232135.
5. Newman, Mark. EJ; Strogatz, SH; Watts, DJ (2001). "Gráficos aleatorios con distribuciones de grado arbitrario y sus aplicaciones". Physical Review E . 64 (2): 026118. arXiv : cond-mat/0007235 . Bibcode :2001PhRvE..64b6118N. doi :10.1103/PhysRevE.64.026118. PMID  11497662. S2CID  360112., Ecuación (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 American Mathematical Society . 19 : A-382.
8. Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (abril de 2003). "Generación de redes correlacionadas a partir de redes no correlacionadas". Physical Review 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). "Camarillas en grafos aleatorios". Actas matemáticas de la Cambridge Philosophical Society . 80 (3): 419–427. Bibcode :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". Physics Reports . 578 : 12. arXiv : 1504.02898 . Bibcode :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 grafos 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 (1997-04-01). "Excursiones brownianas, grafos aleatorios críticos y el coalescente multiplicativo". Anales de probabilidad . 25 (2). doi : 10.1214/aop/1024404421 . ISSN  0091-1798. S2CID  16578106.

Literatura

• West, 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