Gráfico aleatorio

Gráfico generado por un proceso aleatorio.

En matemáticas , gráfico aleatorio es el término general para referirse a las 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 la probabilidad . 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 es necesario modelar redes complejas ; por eso 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, gráfico aleatorio se refiere casi exclusivamente al modelo de gráfico aleatorio 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] 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 arista posible ocurre independientemente con probabilidad 0 < p < 1. La probabilidad de obtener cualquier gráfico aleatorio particular con m aristas es con la notación . ^[4] ${\displaystyle p^{m}(1-p)^{N-m}}$ ${\displaystyle N={\tbinom {n}{2}}}$

Un modelo estrechamente relacionado, el modelo Erdős-Rényi denotado G ( n , M ), asigna igual probabilidad a todos los gráficos con exactamente M aristas. Con 0 ≤ M ≤ N , G ( n , M ) tiene elementos y cada elemento ocurre con probabilidad . ^[3] El último modelo puede verse como una instantánea en un momento particular ( M ) del proceso del 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 de el conjunto de aristas faltantes. ${\displaystyle {\tbinom {N}{M}}}$ ${\displaystyle 1/{\tbinom {N}{M}}}$ ${\displaystyle {\tilde {G}}_{n}}$

Si, en cambio, comenzamos con un conjunto infinito de vértices y nuevamente dejamos que cada arista posible ocurra de forma independiente con probabilidad 0 < p < 1, entonces obtenemos un objeto G llamado gráfico aleatorio infinito . Excepto en los casos triviales en los que p es 0 o 1, es casi seguro que tal G tiene la siguiente propiedad:

Dados n + m elementos , hay un vértice c en V que es adyacente a cada uno de ellos y no es adyacente a ninguno de ellos . ${\displaystyle a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V}$ ${\displaystyle a_{1},\ldots ,a_{n}}$ ${\displaystyle b_{1},\ldots ,b_{m}}$

Resulta que si el conjunto de vértices es contable entonces hay, hasta el isomorfismo , un solo gráfico con esta propiedad, a saber, el gráfico de Rado . Por lo tanto, cualquier gráfico aleatorio contablemente 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 a cada vértice un vector real . La probabilidad de una arista uv entre cualesquiera vértices u y v es alguna función del producto escalar 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 de que un borde determinado exista 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. ${\displaystyle p_{i,j}}$ ${\displaystyle e_{i,j}}$

Para M ≃ pN , donde N es el número máximo de aristas posibles, los dos modelos más utilizados, G ( n , M ) y G ( n , p ), son casi intercambiables. ^[5]

Los gráficos aleatorios regulares forman un caso especial, con propiedades que pueden diferir de los gráficos aleatorios en general.

Una vez que tenemos un modelo de gráficas aleatorias, cada función en las gráficas se convierte en una variable aleatoria . El estudio de este modelo consiste en determinar si, o al menos estimar la probabilidad de que, pueda ocurrir 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 gráficos aleatorios estudia las propiedades típicas de los gráficos aleatorios, aquellas que se cumplen con alta probabilidad para los gráficos extraídos de una distribución particular. Por ejemplo, podríamos preguntar por un valor dado de y cuál es la probabilidad de que esté conectado . Al estudiar estas cuestiones, los investigadores suelen concentrarse en el comportamiento asintótico de las gráficas aleatorias: los valores a los que convergen diversas probabilidades a medida que crecen. La teoría de la percolación caracteriza la conectividad de gráficos aleatorios, especialmente los infinitamente grandes. ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle G(n,p)}$ ${\displaystyle n}$

La percolación está relacionada con la robustez del gráfico (llamado también red). Dado un gráfico aleatorio de nodos y un grado promedio . A continuación eliminamos aleatoriamente una fracción de nodos y dejamos solo una fracción . Existe un umbral de filtración crítico por debajo del cual la red se fragmenta, mientras que por encima existe un componente gigante conectado. ^{[1] [5] [6] [7] [8]} ${\displaystyle n}$ ${\displaystyle \langle k\rangle }$ ${\displaystyle 1-p}$ ${\displaystyle p}$ ${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$ ${\displaystyle p_{c}}$

La percolación localizada se refiere a eliminar un nodo de sus vecinos, los vecinos más cercanos, etc., hasta que se elimine una fracción de los nodos de la red. Se demostró que para un gráfico aleatorio con distribución de grados de Poisson es exactamente igual que para la eliminación aleatoria. ${\displaystyle 1-p}$ ${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$

Las gráficas aleatorias se usan ampliamente en el método probabilístico , donde se intenta probar la existencia de gráficas 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áficas regulares aleatorias , son el conjunto de gráficas regulares tales que y son los números naturales, y es par. ^[3] ${\displaystyle G(n,r-reg)}$ ${\displaystyle r}$ ${\displaystyle r=r(n)}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle 3\leq r<n}$ ${\displaystyle rn=2m}$

La secuencia de grados de un gráfico depende solo del número de aristas en los conjuntos ^[3] ${\displaystyle G}$ ${\displaystyle G^{n}}$

${\displaystyle V_{n}^{(2)}=\left\{ij\ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.}$

Si los bordes, en un gráfico aleatorio, son lo suficientemente grandes como para garantizar que casi todos tengan un grado mínimo de al menos 1, entonces casi todos están conectados y, si son pares, casi todos tienen una coincidencia 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 vuelve conectado. ^[3] ${\displaystyle M}$ ${\displaystyle G_{M}}$ ${\displaystyle G_{M}}$ ${\displaystyle G_{M}}$ ${\displaystyle n}$ ${\displaystyle G_{M}}$

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 bordes y con una probabilidad cercana a 1 garantiza que el gráfico tenga una coincidencia completa, con excepción de como máximo un vértice. . ${\displaystyle {\tfrac {n}{4}}\log(n)}$

Para algunas constantes , casi todos los gráficos etiquetados con vértices y al menos aristas son hamiltonianos . Con la probabilidad tendiendo a 1, la arista particular que aumenta el grado mínimo a 2 hace que el gráfico sea hamiltoniano. ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle cn\log(n)}$

Las propiedades del gráfico aleatorio pueden cambiar o permanecer invariantes bajo las transformaciones del gráfico. 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 lineales) produce un conjunto de gráficos con casi la misma distribución de grados, pero con correlaciones de grado y una agrupación significativamente mayor. coeficiente. ^[9]

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 es adyacente al vértice 1, en caso contrario tiene el color 2, etc.). ^[3] Hasta ahora se desconoce el número de coloraciones adecuadas de gráficos aleatorios dado un número de q colores, llamado polinomio cromático . El escalado 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. ^[10]

á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 . Los tipos de árboles aleatorios incluyen árbol de expansión uniforme , árbol de expansión mínimo aleatorio , árbol binario aleatorio , treap , árbol aleatorio de exploración rápida , árbol browniano y bosque aleatorio .

Gráficos aleatorios condicionales

Considere un modelo de gráfico aleatorio dado definido en el espacio de probabilidad y sea una función de valor real que asigna a cada gráfico en un vector de m propiedades. Para un fijo , los gráficos aleatorios condicionales son modelos en los que la medida de probabilidad asigna probabilidad cero a todos los gráficos tales que ' . ${\displaystyle (\Omega ,{\mathcal {F}},P)}$ ${\displaystyle {\mathcal {P}}(G):\Omega \rightarrow R^{m}}$ ${\displaystyle \Omega }$ ${\displaystyle \mathbf {p} \in R^{m}}$ ${\displaystyle P}$ ${\displaystyle {\mathcal {P}}(G)\neq \mathbf {p} }$

Los casos especiales son gráficos aleatorios condicionalmente uniformes , donde asigna la misma probabilidad a todos los gráficos que tienen propiedades específicas. Pueden verse como una generalización del modelo de Erdős-Rényi G ( n , M ), cuando la información condicionante no es necesariamente el número de aristas M , sino cualquier otra propiedad gráfica arbitraria . En este caso, hay muy pocos resultados analíticos disponibles y se requiere simulación para obtener distribuciones empíricas de propiedades promedio. ${\displaystyle P}$ ${\displaystyle {\mathcal {P}}(G)}$

Historia

El primer uso de un modelo de gráfico aleatorio fue realizado por Helen Hall Jennings y Jacob Moreno en 1938, donde se consideró un "sociograma aleatorio" (un modelo Erdős-Rényi dirigido) al estudiar la comparación de la fracción de enlaces recíprocos en los datos de su red con el modelo aleatorio. . ^[11] Otro uso, bajo el nombre de "red aleatoria", fue por Ray Solomonoff y Anatol Rapoport en 1951, utilizando un modelo de gráficos dirigidos con grados fijos y adjuntos elegidos aleatoriamente a otros vértices. ^[12]

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" ^[8] e independientemente por Gilbert en su artículo "Random Graphs". ^[6]

Ver también

• Condensación de Bose-Einstein: un enfoque de teoría de redes
• método de cavidad
• Redes complejas
• Evolución de doble fase
• Modelo 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 percolación
• Teoría de grafos aleatorios de la gelificación.
• gráfico regular
• Red libre de escala
• Respuesta semilineal
• Modelo de bloque estocástico
• Punto de referencia Lancichinetti-Fortunato-Radicchi

Referencias

1. Bollobás, Béla (2001). Gráficos aleatorios (2ª ed.). Prensa de la Universidad de Cambridge.
2. Friso, Alan; Karonski, Michal (2015). Introducción a los gráficos aleatorios . Prensa de la Universidad de Cambridge.
3. Béla Bollobás , Gráficos aleatorios , 1985, Academic Press Inc., London Ltd.
4. Béla Bollobás , Combinatoria probabilística y sus aplicaciones , 1991, Providence, RI: Sociedad Matemática Estadounidense.
5. Bollobas, B. y Riordan, OM "Resultados matemáticos en gráficos aleatorios sin escala" en "Handbook of Graphs and Networks" (S. Bornholdt y HG Schuster (eds)), Wiley VCH, Weinheim, 1.ª ed., 2003
6. Gilbert, EN (1959), "Gráficos aleatorios", Annals of Mathematical Statistics , 30 (4): 1141–1144, doi : 10.1214/aoms/1177706098.
7. Newman, MEJ (2010). Redes: una introducción . Oxford.
8. Erdős, P. Rényi, A (1959) "Sobre gráficos aleatorios I" en Publ. Matemáticas. Debrecen 6, pág. 290–297 [1] Archivado el 7 de agosto de 2020 en Wayback Machine.
9. Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003). "Generación de redes correlacionadas a partir de redes no correlacionadas". Física. Rev. E. 67 (46107): 046107. arXiv : cond-mat/0212469 . Código bibliográfico : 2003PhRvE..67d6107R. doi : 10.1103/PhysRevE.67.046107. PMID  12786436. S2CID  33054818.
10. Van Bussel, Frank; Ehrlich, Christoph; Fliegner, Denny; Stolzenberg, Sebastián; Timme, Marc (2010). "Polinomios cromáticos de gráficos aleatorios". J. Física. R: Matemáticas. Teor . 43 (17): 175002. arXiv : 1709.06209 . Código Bib : 2010JPhA...43q5002V. doi :10.1088/1751-8113/43/17/175002. S2CID  15723612.
11. Moreno, Jacob L; Jennings, Helen Hall (enero de 1938). «Estadísticas de Configuraciones Sociales» (PDF) . Sociometría . 1 (3/4): 342–374. doi :10.2307/2785588. JSTOR  2785588.
12. Salomónoff, Ray; Rapoport, Anatol (junio de 1951). "Conectividad de redes aleatorias". Boletín de Biofísica Matemática . 13 (2): 107–117. doi :10.1007/BF02478357.