En matemáticas , gráfico aleatorio es el término general para referirse a distribuciones de probabilidad sobre gráficos . Los gráficos aleatorios pueden describirse simplemente mediante una distribución de probabilidad o mediante un proceso aleatorio que los genera. [1] [2] La teoría de gráficos aleatorios se encuentra en la intersección entre la teoría de grafos y la teoría de probabilidades . Desde una perspectiva matemática, los gráficos aleatorios se utilizan para responder preguntas sobre las propiedades de los gráficos típicos . Sus aplicaciones prácticas se encuentran en todas las áreas en las que redes complejasnecesitan ser modelados; por lo tanto, se conocen muchos modelos de gráficos aleatorios, que reflejan los diversos tipos de redes complejas que se encuentran en diferentes áreas. En un contexto matemático, el gráfico aleatorio se refiere casi exclusivamente al modelo de gráfico aleatorio de Erdős-Rényi . En otros contextos, cualquier modelo de gráfico puede denominarse gráfico aleatorio .
Modelos
Un gráfico aleatorio se obtiene comenzando con un conjunto de n vértices aislados y agregando aristas sucesivas entre ellos al azar. El objetivo del estudio en este campo es determinar en qué etapa es probable que surja una propiedad particular del gráfico. [3] Los diferentes modelos de gráficos aleatorios producen diferentes distribuciones de probabilidad en los gráficos. El más comúnmente estudiado es el propuesto por Edgar Gilbert , denotado G ( n , p ), en el que cada borde posible ocurre independientemente con probabilidad 0 < p <1. La probabilidad de obtener cualquier gráfico aleatorio particular con m bordes es con la notación . [4]
Un modelo estrechamente relacionado, el modelo Erdős-Rényi denotado G ( n , M ), asigna la misma probabilidad a todas las gráficas con exactamente M aristas. Con 0 ≤ M ≤ N , G ( n , M ) tiene elementos y cada elemento ocurre con probabilidad . [3] El último modelo se puede ver como una instantánea en un momento particular ( M ) del proceso de gráfico aleatorio. , que es un proceso estocástico que comienza con n vértices y sin aristas, y en cada paso agrega una nueva arista elegida uniformemente del conjunto de aristas faltantes.
Si, en cambio, comenzamos con un conjunto infinito de vértices, y nuevamente dejamos que cada borde posible ocurra independientemente con probabilidad 0 < p <1, entonces obtenemos un objeto G llamado grafo aleatorio infinito . Excepto en los casos triviales en los que p es 0 o 1, tal G casi seguramente tiene la siguiente propiedad:
Dados cualesquiera n + m elementos, hay un vértice c en V que es adyacente a cada uno de y no es adyacente a ninguno de .
Resulta que si el conjunto de vértices es contable , hasta el isomorfismo , solo hay un solo gráfico con esta propiedad, a saber, el gráfico de Rado . Por lo tanto, cualquier gráfico aleatorio numerablemente infinito es casi con seguridad el gráfico de Rado, que por esta razón a veces se denomina simplemente gráfico aleatorio . Sin embargo, el resultado análogo no es cierto para gráficos incontables, de los cuales hay muchos gráficos (no isomórficos) que satisfacen la propiedad anterior.
Otro modelo, que generaliza el modelo de gráfico aleatorio de Gilbert, es el modelo de producto escalar aleatorio . Un gráfico de producto escalar aleatorio asocia con cada vértice un vector real . La probabilidad de un borde uv entre cualesquiera vértices u y v es una función del producto de punto u • v de sus respectivos vectores.
La matriz de probabilidad de la red modela gráficos aleatorios a través de probabilidades de borde, que representan la probabilidad que una ventaja dada existe durante un período de tiempo específico. Este modelo es extensible a dirigido y no dirigido; ponderado y no ponderado; y estructura de gráficos estáticos o dinámicos.
Para M ≃ pN , donde N es el número máximo posible de aristas, los dos modelos más utilizados, G ( n , M ) y G ( n , p ), son casi intercambiables. [5]
Los gráficos regulares aleatorios forman un caso especial, con propiedades que pueden diferir de los gráficos aleatorios en general.
Una vez que tenemos un modelo de gráficos aleatorios, cada función en los gráficos se convierte en una variable aleatoria . El estudio de este modelo es para determinar si, o al menos estimar la probabilidad de que ocurra una propiedad. [4]
Terminología
El término "casi todos" en el contexto de gráficos aleatorios se refiere a una secuencia de espacios y probabilidades, de modo que las probabilidades de error tienden a cero. [4]
Propiedades
La teoría de las gráficas aleatorias estudia las propiedades típicas de las gráficas aleatorias, aquellas que se mantienen con alta probabilidad para las gráficas extraídas de una distribución particular. Por ejemplo, podríamos pedir un valor dado de y cual es la probabilidad de que está conectado . Al estudiar estas preguntas, los investigadores a menudo se concentran en el comportamiento asintótico de los gráficos aleatorios, los valores a los que convergen varias probabilidades comocrece muy grande. La teoría de la filtración caracteriza la conectividad de los gráficos aleatorios, especialmente los infinitamente grandes.
La percolación está relacionada con la robustez del gráfico (también llamado red). Dado un gráfico aleatorio de nodos y un grado medio . A continuación, eliminamos aleatoriamente una fracción. de nodos y dejar solo una fracción . Existe un umbral de percolación crítico debajo del cual la red se fragmenta mientras que arriba existe un componente gigante conectado. [1] [5] [6] [7] [8] [9]
La percolación localizada se refiere a eliminar un nodo de sus vecinos, los vecinos más cercanos, etc.hasta una fracción de de nodos de la red se elimina. Se demostró que para gráficos aleatorios con distribución de grados de Poissonexactamente como para la eliminación aleatoria. Para otros tipos de distribuciones de títulospara el ataque localizado es diferente del ataque aleatorio [10] (funciones de umbral, evolución de)
Los gráficos aleatorios se utilizan ampliamente en el método probabilístico , donde se intenta probar la existencia de gráficos con ciertas propiedades. La existencia de una propiedad en un gráfico aleatorio a menudo puede implicar, a través del lema de regularidad de Szemerédi , la existencia de esa propiedad en casi todos los gráficos.
En gráficos regulares aleatorios , son el conjunto de -Gráficos regulares con tal que y son los números naturales, , y incluso. [3]
La secuencia de grados de un gráfico en depende solo del número de aristas en los conjuntos [3]
Si bordes, en un gráfico aleatorio, es lo suficientemente grande para garantizar que casi todos tiene un grado mínimo de al menos 1, luego casi todos está conectado y, si es parejo, casi todos tiene una combinación perfecta. En particular, en el momento en que el último vértice aislado desaparece en casi todos los gráficos aleatorios, el gráfico se conecta. [3]
Casi todos los procesos de gráficos en un número par de vértices con el borde elevando el grado mínimo a 1 o un gráfico aleatorio con un poco más de aristas y con probabilidad cercana a 1 asegura que el gráfico tenga una coincidencia completa, con la excepción de como máximo un vértice.
Por alguna constante , casi todos los gráficos etiquetados con vértices y al menos bordes es hamiltoniano . Con la probabilidad tendiendo a 1, el borde particular que aumenta el grado mínimo a 2 hace que el gráfico sea hamiltoniano.
Las propiedades del gráfico aleatorio pueden cambiar o permanecer invariantes bajo transformaciones de gráficos. Mashaghi A. et al., Por ejemplo, demostraron que una transformación que convierte gráficos aleatorios en sus gráficos de borde dual (o gráficos de líneas) produce un conjunto de gráficos con casi la misma distribución de grados, pero con correlaciones de grados y una agrupación significativamente más alta. coeficiente. [11]
Colorante
Dado un gráfico aleatorio G de orden n con el vértice V ( G ) = {1, ..., n }, mediante el algoritmo codicioso sobre el número de colores, los vértices se pueden colorear con los colores 1, 2, ... (el vértice 1 tiene el color 1, el vértice 2 tiene el color 1 si no está adyacente al vértice 1, de lo contrario, el color 2, etc.). [3] El número de coloraciones adecuadas de gráficos aleatorios dado un número de q colores, llamado polinomio cromático , sigue siendo desconocido hasta ahora. La escala de ceros del polinomio cromático de gráficos aleatorios con parámetros n y el número de aristas m o la probabilidad de conexión p se ha estudiado empíricamente utilizando un algoritmo basado en la coincidencia de patrones simbólicos. [12]
Árboles aleatorios
Un árbol aleatorio es un árbol o arborescencia que se forma mediante un proceso estocástico . En una amplia gama de gráficos aleatorios de orden n y tamaño M ( n ), la distribución del número de componentes del árbol de orden k es asintóticamente Poisson . Tipos de árboles al azar incluyen árbol de expansión uniforme , árbol de expansión mínima al azar , árbol binario al azar , Treap , rápidamente explorar el árbol al azar , árbol Browniano , y los bosques al azar .
Gráficos aleatorios condicionales
Considere un modelo de gráfico aleatorio dado definido en el espacio de probabilidad y deja ser una función de valor real que asigna a cada gráfico en un vector de m propiedades. Por un fijo, los gráficos aleatorios condicionales son modelos en los que la medida de probabilidad asigna probabilidad cero a todos los gráficos de manera que '.
Los casos especiales son gráficos aleatorios condicionalmente uniformes , dondeasigna la misma probabilidad a todos los gráficos que tienen propiedades específicas. Pueden verse como una generalización del modelo G ( n , M ) de Erdős-Rényi , cuando la información de condicionamiento no es necesariamente el número de aristas M , sino cualquier otra propiedad gráfica arbitraria. En este caso, se dispone de muy pocos resultados analíticos y se requiere simulación para obtener distribuciones empíricas de propiedades promedio.
Gráficos interdependientes
En gráficos interdependientes, los nodos de una red (gráfico) dependen de otras redes para funcionar. Por lo tanto, las fallas en uno o varios gráficos inducen fallas en cascada entre los gráficos que pueden conducir a un colapso abrupto. [13] [14]
Historia
El primer uso de un modelo de gráfico aleatorio fue por Helen Hall Jennings y Jacob Moreno en 1938, donde se consideró un "sociograma de azar" (un modelo dirigido de Erdős-Rényi) al estudiar la comparación de la fracción de enlaces recíprocos en sus datos de red con el modelo aleatorio. . [15] Otro uso, bajo el nombre de "red aleatoria", fue por Solomonoff y Rapoport en 1951, utilizando un modelo de gráficos dirigidos con grados fijos y adjuntos elegidos aleatoriamente a otros vértices. [dieciséis]
El modelo Erdős-Rényi de gráficos aleatorios fue definido por primera vez por Paul Erdős y Alfréd Rényi en su artículo de 1959 "On Random Graphs" [9] e independientemente por Gilbert en su artículo "Random graphs". [6]
Ver también
- Condensación de Bose-Einstein: un enfoque de la teoría de redes
- Método de la cavidad
- Redes complejas
- Evolución de doble fase
- Modelo de Erdős – Rényi
- Modelo de gráfico aleatorio exponencial
- Teoría de grafos
- Redes interdependientes
- Ciencia de la red
- Filtración
- Teoría de la filtración
- Teoría de la gelificación de grafos aleatorios
- Gráfico regular
- Escale la red libre
- Respuesta semilineal
- Modelo de bloque estocástico
- Punto de referencia Lancichinetti – Fortunato – Radicchi
Referencias
- ↑ a b Bollobás, Béla (2001). Gráficos aleatorios (2ª ed.). Prensa de la Universidad de Cambridge.
- ^ Frieze, Alan; Karonski, Michal (2015). Introducción a los gráficos aleatorios . Prensa de la Universidad de Cambridge.
- ^ a b c d e f Béla Bollobás , Random Graphs , 1985, Academic Press Inc., London Ltd.
- ^ a b c Béla Bollobás , Combinatoria probabilística y sus aplicaciones , 1991, Providence, RI: American Mathematical Society.
- ^ a b Bollobas, B. y Riordan, OM "Resultados matemáticos en gráficos aleatorios sin escala" en "Manual de gráficos y redes" (S. Bornholdt y HG Schuster (eds)), Wiley VCH, Weinheim, 1ª ed., 2003
- ^ a b Gilbert, EN (1959), "Gráficos aleatorios", Annals of Mathematical Statistics , 30 (4): 1141-1144, doi : 10.1214 / aoms / 1177706098.
- ^ 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.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ a b Erdős, P. Rényi, A (1959) "Sobre gráficos aleatorios I" en Publ. Matemáticas. Debrecen 6, pág. 290-297 [1]
- ^ Shao, Shuai; Huang, Xuqing; Stanley, H Eugene; Havlin, Shlomo (2015). "Percolación de ataque localizado en redes complejas". Nueva Revista de Física . 17 (2): 023049. arXiv : 1412.3124 . Código Bibliográfico : 2015NJPh ... 17b3049S . doi : 10.1088 / 1367-2630 / 17/2/023049 . ISSN 1367-2630 .
- ^ Ramezanpour, A .; Karimipour, V .; Mashaghi, A. (2003). "Generación de redes correlacionadas a partir de redes no correlacionadas". Phys. Rev. E . 67 (46107): 046107. arXiv : cond-mat / 0212469 . Código Bibliográfico : 2003PhRvE..67d6107R . doi : 10.1103 / PhysRevE.67.046107 . PMID 12786436 .
- ^ Van Bussel, Frank; Ehrlich, Christoph; Fliegner, Denny; Stolzenberg, Sebastián; Timme, Marc (2010). "Polinomios cromáticos de gráficos aleatorios". J. Phys. A: Matemáticas. Theor . 43 (17): 175002. arXiv : 1709.06209 . Código bibliográfico : 2010JPhA ... 43q5002V . doi : 10.1088 / 1751-8113 / 43/17/175002 .
- ^ Buldyrev, Sergey V .; Parshani, Roni; Paul, Gerald; Stanley, H. Eugene; Havlin, Shlomo (2010). "Cascada catastrófica de fallas en redes interdependientes". Naturaleza . 464 (7291): 1025–1028. arXiv : 1012.0206 . Código Bibliográfico : 2010Natur.464.1025B . doi : 10.1038 / nature08932 . ISSN 0028-0836 . PMID 20393559 .
- ^ Gao, Jianxi; Buldyrev, Sergey V .; Stanley, H. Eugene; Havlin, Shlomo (2011). "Redes formadas a partir de redes interdependientes". Física de la naturaleza . 8 (1): 40–48. Código bibliográfico : 2012NatPh ... 8 ... 40G . CiteSeerX 10.1.1.379.8214 . doi : 10.1038 / nphys2180 . ISSN 1745-2473 .
- ^ Moreno, Jacob L; Jennings, Helen Hall (enero de 1938). "Estadísticas de Configuraciones Sociales". Sociometría . 1 (3/4): 342–374. doi : 10.2307 / 2785588 . JSTOR 2785588 .
- ^ Solomonoff, Ray; Rapopst, Anatol (junio de 1951). "Conectividad de redes aleatorias". Boletín de Biofísica Matemática . 13 (2): 107-117. doi : 10.1007 / BF02478357 .