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, [1] [2] mientras que Edgar Gilbert introdujo el otro modelo de forma contemporánea e independiente de Erdős y Rényi. [3]En el modelo de Erdős y Rényi, todas las gráficas en un conjunto de vértices fijo con un número fijo de aristas son igualmente probables; en el modelo presentado por Gilbert, cada borde tiene una probabilidad fija de estar presente o ausente, independientemente de los otros bordes. Estos modelos se pueden utilizar 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 mantenga en 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 modelo, un gráfico se elige uniformemente al azar de la colección de todos los gráficos que tienen nodos y bordes. 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 bordes en tres vértices etiquetados (uno para cada elección del vértice medio en una ruta de dos bordes), y cada uno de estos tres gráficos se incluye con probabilidad .
- En el modelo, un gráfico se construye conectando nodos etiquetados al azar. Cada borde se incluye en el gráfico con probabilidad, independientemente de todos los demás bordes. De manera equivalente, la probabilidad de generar cada gráfico que tiene nodos y bordes es El parámetro en este modelo se puede pensar como una función de ponderación; como 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 donde todos gráficos en los vértices se eligen con la misma probabilidad.
El comportamiento de los gráficos aleatorios se estudia a menudo en el caso en que , el número de vértices, tiende a infinito. Aunque y En este caso pueden ser arreglados, también pueden ser funciones dependiendo de . Por ejemplo, la afirmación de que casi todas las gráficas de está conectado significa que, como tiende a infinito, la probabilidad de que una gráfica en vértices con probabilidad de borde está conectado 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 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 2 → ∞, entonces G ( n , p ) debería comportarse de manera similar a G ( n , M ) cona medida que n aumenta.
Este es el caso de muchas propiedades gráficas. Si P es una propiedad de gráfico que es monótona con respecto al orden del subgráfico (lo que significa que si A es un subgrafo de B y A satisface P , entonces B también satisfará a P ), entonces los enunciados " P se cumple 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 2 → ∞). Por ejemplo, esto es válido si P es la propiedad de estar conectado , o si P es la propiedad de contener un ciclo hamiltoniano . Sin embargo, esto no se mantendrá 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 que se usa más comúnmente en la actualidad, en parte debido a la facilidad de análisis que permite la independencia de los bordes.
Propiedades de G ( n , p )
Con la notación anterior, una gráfica en G ( n , p ) tiene en promediobordes. La distribución del grado de cualquier vértice en particular es binomial : [4]
donde n es el número total de vértices en el gráfico. Desde
esta distribución es de Poisson para n grandes y np = const.
En un artículo de 1960, Erdős y Rényi [5] 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 una gráfica 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 una gráfica en G ( n , p ) casi seguramente tendrá un componente gigante único que contiene 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.
- Si , entonces es casi seguro que un gráfico en G ( n , p ) esté conectado.
Por lo tanto es un umbral agudo para la conectividad de G ( n , p ).
Otras propiedades del gráfico se pueden describir casi con precisión ya que 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 seguramente tamaño k ( n ) o k ( n ) + 1. [ 6]
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 más alto . [7]
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 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). Dado que 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 celosías de los espacios euclidianos. La transición en np = 1 de componente gigante a componente pequeño tiene análogos para estos gráficos, pero para las celosías, 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 . Así, el proceso 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, este todavía sería 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 gráfico, visto como una red de comunicación. Dado un gráfico aleatorio de n ≫ 1 nodos con un grado promedio . Eliminar aleatoriamente una fracción de nodos y dejar solo una fracción de la red. Existe un umbral de percolación crítico debajo del cual la red se fragmenta mientras que arriba existe un componente gigante conectado de orden n . El tamaño relativo del componente gigante, P ∞ , viene dado por [5] [1] [2] [8]
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 bajo agrupamiento, a diferencia de muchas redes sociales. [ cita requerida ] Algunas alternativas de modelado incluyen el modelo Barabási-Albert y el modelo Watts y Strogatz . Estos modelos alternativos no son procesos de filtración, sino que representan un modelo de crecimiento y recableado, respectivamente. Buldyrev et al. Desarrollaron recientemente un modelo para la interacción de las redes Erdős-Rényi . [9]
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ó a continuación en 1960.
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 infinito 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 fase dual : un 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.
- Los modelos de gráficos aleatorios exponenciales describen 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 bloque estocástico , una generalización del modelo de Erdős-Rényi para grafos con estructura de comunidad latente
- Modelo Watts-Strogatz
- Modelo de Barabási-Albert
Referencias
- ^ a b Erdős, P .; Rényi, A. (1959). "Sobre gráficos aleatorios. I" (PDF) . Publicationes Mathematicae . 6 : 290-297.
- ^ a b Bollobás, B. (2001). Gráficos aleatorios (2ª ed.). Prensa de la Universidad de Cambridge. ISBN 0-521-79722-5.
- ^ a b Gilbert, EN (1959). "Gráficos aleatorios" . Anales de estadística matemática . 30 (4): 1141-1144. doi : 10.1214 / aoms / 1177706098 .
- ^ Newman, Mark. EJ; Strogatz, SH; Watts, DJ (2001). "Gráficos aleatorios con distribuciones de grados arbitrarias y sus aplicaciones". Revisión E física . 64 : 026118. arXiv : cond-mat / 0007235 . Código bibliográfico : 2001PhRvE..64b6118N . doi : 10.1103 / PhysRevE.64.026118 . PMID 11497662 ., Eq. (1)
- ^ a b 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.La probabilidad p usada aquí se refiere allí a
- ^ Matula, David W. (febrero de 1972). "El problema de la fiesta de los empleados". Avisos de la Sociedad Matemática Estadounidense . 19 : A-382.
- ^ Ramezanpour, A .; Karimipour, V .; Mashaghi, A. (abril de 2003). "Generación de redes correlacionadas a partir de redes no correlacionadas". Revisión E física . 67 (4): 046107. arXiv : cond-mat / 0212469 . Código Bibliográfico : 2003PhRvE..67d6107R . doi : 10.1103 / PhysRevE.67.046107 . PMID 12786436 .
- ^ Bollobás, B .; Erds, P. (1976). "Cliques en gráficos aleatorios". Procedimientos matemáticos de la Sociedad Filosófica de Cambridge . 80 (3): 419–427. Código Bibliográfico : 1976MPCPS..80..419B . doi : 10.1017 / S0305004100053056 .
- ^ Buldyrev, SV; Parshani, R .; Paul, G .; Stanley, HE; Havlin, S. (2010). "Cascada catastrófica de fallas en redes interdependientes" . Naturaleza . 464 (7291): 1025–8. arXiv : 0907.1182 . Código Bibliográfico : 2010Natur.464.1025B . doi : 10.1038 / nature08932 . PMID 20393559 .
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.
- Reuven Cohen y Shlomo Havlin (2010). Redes complejas: estructura, robustez y función . Prensa de la Universidad de Cambridge.
Enlaces web
- Vídeo: Gráfico aleatorio de Erdos-Renyi