stringtranslate.com

Modelo de Erdős-Rényi

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

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)

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 .

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 2 → ∞, entonces G ( n , p ) debería comportarse de manera similar a G ( n , M ) con a medida que n aumenta.

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 ( np )" y " P se cumple para casi todos los grafos en " son equivalentes (siempre que pn 2 → ∞). 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).

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]

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

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

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

Por lo tanto, existe un umbral claro para la conectividad de G ( n , p ).

Otras propiedades del grafo pueden describirse casi con precisión cuando n tiende a infinito. Por ejemplo, hay un k ( n ) (aproximadamente igual a 2log 2 ( 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 los bordes (o enlaces) de forma aleatoria. 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]

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 ( np ) 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 ( nM ), 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:

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 .

Véase también

Referencias

  1. ^ ab Erdős, P.; Rényi, A. (1959). "Sobre grafos aleatorios. I" (PDF) . Publicationes Mathematicae . 6 (3–4): 290–297. doi :10.5486/PMD.1959.6.3-4.12. S2CID  253789267. Archivado (PDF) desde el original el 2020-08-07 . Consultado el 2011-02-23 .
  2. ^ ab Bollobás, B. (2001). Grafos aleatorios (2.ª ed.). Cambridge University Press. ISBN 0-521-79722-5.
  3. ^ ab 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. ^ ab 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
  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. ^ ab 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 (1 de abril de 1997). "Excursiones brownianas, grafos aleatorios críticos y coalescencia multiplicativa". Anales de probabilidad . 25 (2). doi : 10.1214/aop/1024404421 . ISSN  0091-1798. S2CID  16578106.

Literatura

Enlaces externos