Gráfico aleatorio

En matemáticas , grafo aleatorio es el término general para referirse a distribuciones de probabilidad sobre grafos . Los grafos aleatorios pueden describirse simplemente por una distribución de probabilidad o por un proceso aleatorio que los genera. ^[1]^[2] La teoría de grafos aleatorios se encuentra en la intersección entre la teoría de grafos y la teoría de probabilidad . Desde una perspectiva matemática, los grafos aleatorios se utilizan para responder preguntas sobre las propiedades de los grafos típicos . Sus aplicaciones prácticas se encuentran en todas las áreas en las que se necesitan modelar redes complejas ; por lo tanto, se conocen muchos modelos de grafos aleatorios, que reflejan los diversos tipos de redes complejas que se encuentran en diferentes áreas. En un contexto matemático, grafo aleatorio se refiere casi exclusivamente al modelo de grafo aleatorio de Erdős–Rényi . En otros contextos, cualquier modelo de grafo puede denominarse grafo aleatorio .

Modelos

Un grafo aleatorio se obtiene partiendo de un conjunto de n vértices aislados y añadiendo 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 grafo. ^[3] Diferentes modelos de grafos aleatorios producen diferentes distribuciones de probabilidad en los grafos. El más estudiado es el propuesto por Edgar Gilbert pero a menudo llamado modelo de Erdős–Rényi , denotado G ( n , p ). En él, cada arista posible ocurre independientemente con probabilidad 0 < p < 1. La probabilidad de obtener cualquier grafo aleatorio particular con m aristas es con la notación . ^[4] $p^{m}(1-p)^{N-m}$ $N={\tbinom {n}{2}}$

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

Si, en cambio, empezamos con un conjunto infinito de vértices y, de nuevo, dejamos que cada posible arista ocurra independientemente con una probabilidad de 0 < p < 1, obtenemos un objeto G llamado grafo aleatorio infinito . Excepto en los casos triviales en los que p es 0 o 1, es casi seguro que un grafo de este tipo tenga la siguiente propiedad:

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

Resulta que si el conjunto de vértices es numerable, entonces existe, salvo isomorfismo , un único grafo con esta propiedad, a saber, el grafo de Rado . Por lo tanto, cualquier grafo aleatorio infinito numerable es casi con toda seguridad el grafo de Rado, que por esta razón a veces se denomina simplemente grafo aleatorio . Sin embargo, el resultado análogo no es cierto para grafos incontables, de los cuales hay muchos grafos (no isomorfos) que satisfacen la propiedad anterior.

Otro modelo, que generaliza el modelo de grafo aleatorio de Gilbert, es el modelo de producto escalar aleatorio . Un grafo de producto escalar aleatorio asocia con 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 red modela gráficos aleatorios a través de probabilidades de aristas, que representan la probabilidad de que exista una arista dada durante un período de tiempo específico. Este modelo es extensible a estructuras de gráficos dirigidos y no dirigidos, ponderados y no ponderados, estáticos o dinámicos. $p_{i,j}$ $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 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 consiste en determinar si una propiedad puede ocurrir o al menos estimar la probabilidad de que ocurra. ^[4]

Terminología

El término "casi todos" en el contexto de gráficos aleatorios se refiere a una secuencia de espacios y probabilidades, tales que las probabilidades de error tienden a cero. ^[4]

Propiedades

La teoría de grafos aleatorios estudia las propiedades típicas de los grafos aleatorios, aquellas que se cumplen con alta probabilidad para los grafos 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é conexo . Al estudiar tales cuestiones, los investigadores a menudo se concentran en el comportamiento asintótico de los grafos aleatorios, los valores a los que convergen varias probabilidades a medida que se hace muy grande. La teoría de la percolación caracteriza la conexidad de los grafos aleatorios, especialmente los infinitamente grandes. $n$ $p$ $G(n,p)$ $n$

La percolación está relacionada con la robustez del grafo (también llamado red). Dado un grafo 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 crítico de percolación por debajo del cual la red se fragmenta mientras que por encima existe un componente conectado gigante. ^[1]^[5]^[6]^[7]^[8] $n$ $\langle k\rangle$ $1-p$ $p$ $p_{c}={\tfrac {1}{\langle k\rangle }}$ $p_{c}$

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

Los grafos aleatorios se utilizan ampliamente en el método probabilístico , donde se intenta demostrar la existencia de grafos con ciertas propiedades. La existencia de una propiedad en un grafo aleatorio a menudo puede implicar, a través del lema de regularidad de Szemerédi , la existencia de esa propiedad en casi todos los grafos.

En grafos regulares aleatorios , son el conjunto de grafos regulares con tales que y son los números naturales, y es par. ^[3] $G(n,r-reg)$ $r$ $r=r(n)$ $n$ $m$ $3\leq r<n$ $rn=2m$

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

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

Si las aristas de un grafo aleatorio son lo suficientemente grandes como para garantizar que casi todas tengan un grado mínimo de al menos 1, entonces casi todas son conexas y, si son pares, casi todas tienen una correspondencia perfecta. En particular, en el momento en que el último vértice aislado desaparece en casi todos los grafos aleatorios, el grafo se vuelve conexo. ^[3] $M$ $G_{M}$ $G_{M}$ $G_{M}$ $n$ $G_{M}$

Casi todos los procesos gráficos en un número par de vértices con el borde que eleva 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 garantizan que el gráfico tenga una coincidencia completa, con excepción de como máximo un vértice. ${\tfrac {n}{4}}\log(n)$

Para alguna constante , casi todo grafo etiquetado con vértices y al menos aristas es hamiltoniano . Con una probabilidad que tiende a 1, la arista particular que aumenta el grado mínimo a 2 hace que el grafo sea hamiltoniano. $c$ $n$ $cn\log(n)$

Las propiedades de un grafo aleatorio pueden cambiar o permanecer invariables bajo transformaciones de grafos. Mashaghi A. et al., por ejemplo, demostraron que una transformación que convierte grafos aleatorios en sus grafos de aristas duales (o grafos lineales) produce un conjunto de grafos con una distribución de grados casi igual, pero con correlaciones de grados y un coeficiente de agrupamiento significativamente más alto. ^[9]

Colorante

Dado un grafo aleatorio G de orden n con el vértice V ( G ) = {1, ..., n }, por el algoritmo voraz sobre el número de colores, los vértices pueden ser coloreados con los colores 1, 2, ... (el vértice 1 se colorea 1, el vértice 2 se colorea 1 si no es adyacente al vértice 1, de lo contrario se colorea 2, etc.). ^[3] El número de coloraciones propias de grafos aleatorios dado un número de q colores, llamado su polinomio cromático , sigue siendo desconocido hasta ahora. El escalado de ceros del polinomio cromático de grafos 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 un amplio rango de grafos 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 de Poisson . Los tipos de árboles aleatorios incluyen árbol de expansión uniforme , árbol de expansión mínima aleatoria , árbol binario aleatorio , treap , árbol aleatorio de exploración rápida , árbol browniano y bosque aleatorio .

Gráficos aleatorios condicionales

Consideremos 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 ' . $(\Omega ,{\mathcal {F}},P)$ ${\mathcal {P}}(G):\Omega \rightarrow R^{m}$ $\Omega$ $\mathbf {p} \in R^{m}$ $P$ ${\mathcal {P}}(G)\neq \mathbf {p}$

Los casos especiales son los grafos aleatorios condicionalmente uniformes , donde se asigna la misma probabilidad a todos los grafos 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 de condicionamiento no es necesariamente el número de aristas M , sino cualquier otra propiedad arbitraria del grafo . En este caso, hay muy pocos resultados analíticos disponibles y se requiere simulación para obtener distribuciones empíricas de propiedades promedio. $P$ ${\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 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. ^[11] Otro uso, bajo el nombre de "red aleatoria", fue realizado por Ray Solomonoff y Anatol Rapoport en 1951, utilizando un modelo de gráficos dirigidos con grado de salida fijo y conexiones elegidas 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]

Véase también

Referencias

^ ab 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 . Cambridge University Press.
^ abcdef Béla Bollobás , Gráficos aleatorios , 1985, Academic Press Inc., Londres Ltd.
^ abc Béla Bollobás , Combinatoria probabilística y sus aplicaciones , 1991, Providence, RI: American Mathematical Society.
^ ab 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
^ ab Gilbert, EN (1959), "Gráficos aleatorios", Anales de estadística matemática , 30 (4): 1141–1144, doi : 10.1214/aoms/1177706098.
^ Newman, MEJ (2010). Redes: una introducción . Oxford.
^ ab 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.
^ 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 . Bibcode :2003PhRvE..67d6107R. doi :10.1103/PhysRevE.67.046107. PMID 12786436. S2CID 33054818.
^ Van Bussel, Frank; Ehrlich, Christoph; Fliegner, Denny; Stolzenberg, Sebastian; Timme, Marc (2010). "Polinomios cromáticos de grafos aleatorios". J. Phys. A: Math. Theor . 43 (17): 175002. arXiv : 1709.06209 . Bibcode :2010JPhA...43q5002V. doi :10.1088/1751-8113/43/17/175002. S2CID 15723612.
^ Moreno, Jacob L; Jennings, Helen Hall (enero de 1938). "Estadísticas de configuraciones sociales" (PDF) . Sociometry . 1 (3/4): 342–374. doi :10.2307/2785588. JSTOR 2785588.
^ Solomonoff, 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.