Gráfico 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. La teoría de grafos 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 de Erdős-Rényi. En otros contextos, cualquier modelo de gráfico puede denominarse gráfico aleatorio.

Modelos

Un gráfico al azar se obtiene comenzando con un conjunto de n vertices aislados y la adición de bordes sucesivos entre ellos al azar. El objetivo del estudio en este campo es determinar en qué etapa puede surgir una propiedad particular del gráfico. Diferentes modelos de gráficos aleatorios producir diferentes distribuciones de probabilidad en gráficos. Más comúnmente estudiado es el propuesto por Edgar Gilbert, denotado G()n,p), en que cada borde posible ocurre independientemente con probabilidad 0 p 1. La probabilidad de obtener cualquiera en particular gráfico al azar con m bordes es pm()1− − p)N− − m{displaystyle p^{m}(1-p)} {N-m} con la notación N=()n2){displaystyle N={tbinom {n}{2}}.

Un modelo estrechamente relacionado, el modelo Erdős–Rényi denotó G()n,M), asigna igual probabilidad a todos los gráficos con exactamente M bordes. Con 0 ≤ M ≤ N, G()n,M) tiene ()NM){displaystyle {tbinom {fn}} {fn}} {fn}} {fn}} {fn}} {fn}} elementos y cada elemento ocurre con probabilidad 1/()NM){displaystyle 1/{tbinom {N} {M}}. Este último modelo se puede ver como una instantánea en un momento determinado (M) de la proceso de gráfico aleatorio G~ ~ n{displaystyle {tilde {fn}} {fn}} {fn}} {fn}}} {fn}} {fn}}} {fn}}}} {fn}}}} {fn}}}} {fn}}}}}} {fn}}}}}}}}}}}}}}}, que es un proceso estocástico que comienza con n vértices y sin bordes, y en cada paso añade un nuevo borde elegido uniformemente del conjunto de bordes perdidos.

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, tal G casi seguramente tiene la siguiente propiedad:

Dados n + m elementos a1,...... ,an,b1,...... ,bm▪ ▪ V{displaystyle a_{1},ldotsa_{n},b_{1},ldotsb_{m}in V., hay un vértice c dentro V que está adyacente a cada uno de a1,...... ,an{displaystyle a_{1},ldotsa_{n} y no está adyacente a ninguna de b1,...... ,bm{displaystyle b_{1},ldotsb_{m}.

Resulta que si el conjunto de vértices es contable entonces hay, hasta el isomorfismo, sólo un gráfico con esta propiedad, a saber, el gráfico de Rado. Por lo tanto, cualquier gráfico aleatorio contablemente infinito es casi con toda 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 cualquier vértice u y v es alguna función del producto escalar u • v de sus respectivos vectores.

La matriz de probabilidad de red modelos gráficos aleatorios a través de probabilidades de borde, que representan la probabilidad pi,j{displaystyle p_{i,j} que un borde dado ei,j{displaystyle e_{i,j} existe para un período de tiempo especificado. Este modelo es extensible a la estructura dirigida y no dirigida; ponderada y no ponderada; y estructura gráfica estática o dinámica.

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.

Random regular graphs from a special case, with properties that may differ from random graphs in 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.

Terminología

The term 'almost every n#39; in the context of random graphs refers to a sequence of spaces and probabilities, such that the error probabilities tend to zero.

Propiedades

La teoría de los gráficos aleatorios estudia las propiedades típicas de los gráficos aleatorios, aquellos que tienen una alta probabilidad de gráficos extraídos de una distribución particular. Por ejemplo, podríamos pedir un valor dado de n{displaystyle n} y p{displaystyle p} lo que la probabilidad es que G()n,p){displaystyle G(n,p)} está conectado. Al estudiar tales preguntas, los investigadores a menudo se concentran en el comportamiento asintotico de los gráficos aleatorios, los valores a los que convergen varias probabilidades como n{displaystyle n} crece muy grande. La teoría de la percolación caracteriza la conexión de gráficos aleatorios, especialmente los infinitamente grandes.

La percolación se relaciona con la robustez del gráfico (llamado también red). Dado un gráfico aleatorio n{displaystyle n} nodos y un grado promedio .. k.. {displaystyle langle krangle }. Luego quitamos aleatoriamente una fracción 1− − p{displaystyle 1-p} de los nodos y dejar sólo una fracción p{displaystyle p}. Existe un umbral crítico de percolación pc=1.. k.. {displaystyle p_{c}={tfrac {1}{langle krangle}}} debajo del cual la red se fragmenta mientras arriba pc{displaystyle P_{c} existe un componente conectado gigante.

La percolación localizada se refiere a la eliminación de un nodo de sus vecinos, vecinos más cercanos etc. hasta una fracción de 1− − p{displaystyle 1-p} de los nodos de la red se elimina. Se mostró que para gráfico aleatorio con distribución Poisson de grados pc=1.. k.. {displaystyle p_{c}={tfrac {1}{langle krangle}}} exactamente como para la eliminación aleatoria.

Las gráficas aleatorias se utilizan 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, mediante el lema de regularidad de Szemerédi, la existencia de esa propiedad en casi todos los gráficos.

En gráficos regulares aleatorios, G()n,r− − reg){displaystyle G(n,r-reg)} son el conjunto de r{displaystyle r}-grafos regulares con r=r()n){displaystyle r=r(n)} tales que n{displaystyle n} y m{displaystyle m} son los números naturales, <math alttext="{displaystyle 3leq r3≤ ≤ r.n{displaystyle 3leq r maden}<img alt="{displaystyle 3leq r, y rn=2m{displaystyle rn=2m} es incluso.

La secuencia de grado de un gráfico G{displaystyle G. dentro Gn{displaystyle G^{n} depende sólo del número de bordes en los conjuntos

Vn()2)={}ij:1≤ ≤ j≤ ≤ n,iل ل j}⊂ ⊂ V()2),i=1,⋯ ⋯ ,n.{displaystyle V_{n}{(2)}=left{ij: 1leq jleq n,ineq jright}subset V^{(2)},qquad i=1,cdotsn.}

Si hay bordes, M{displaystyle M} en un gráfico al azar, GM{displaystyle G_{M} es lo suficientemente grande para asegurar que casi todos GM{displaystyle G_{M} tiene un grado mínimo al menos 1, entonces casi todos GM{displaystyle G_{M} está conectado y, si n{displaystyle n} es incluso, casi todos GM{displaystyle G_{M} tiene una combinación perfecta. En particular, el momento en que el último vértice aislado desaparece en casi cada gráfico aleatorio, el gráfico se conecta.

Casi cada proceso gráfico en un número incluso de vértices con el borde elevando el grado mínimo a 1 o un gráfico aleatorio con un poco más que n4log⁡ ⁡ ()n){displaystyle {tfrac {n}log(n)} bordes y con probabilidad cerca de 1 asegura que el gráfico tiene una combinación completa, con excepción de la mayoría de un vértice.

Para algunos constantes c{displaystyle c}, casi todos los gráficos etiquetados con n{displaystyle n} vértices y al menos cnlog⁡ ⁡ ()n){displaystyle cnlog(n)} Los bordes son Hamiltonian. Con la probabilidad que tiende a 1, el borde particular que aumenta el grado mínimo a 2 hace el grafito Hamiltonian.

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.

Colorear

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 se colorea 2, etc.). Hasta ahora se desconoce el número de coloraciones adecuadas de gráficos aleatorios dado un número de colores q, llamado polinomio cromático. Se ha estudiado empíricamente 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. utilizando un algoritmo basado en la coincidencia de patrones simbólicos.

Á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 definido en el espacio de probabilidad ()Ω Ω ,F,P){displaystyle (Omega{mathcal {F}},P)} y dejar P()G):Ω Ω → → Rm{fnMicrosoft Sans Serif} Omega rightarrow R^{m} ser una función real valorada que asigna a cada gráfico en Ω Ω {displaystyle Omega } un vector de m propiedades. Para un fijo p▪ ▪ Rm{displaystyle mathbf {p} in R^{m}, gráficos aleatorios condicionales son modelos en los que la medida de probabilidad P{displaystyle P} asigna cero probabilidad a todos los gráficos de tal manera que 'P()G)ل ل p{displaystyle {mathcal {}(G)neq mathbf {p}.

Casos especiales gráficos aleatorios uniformes condicionalmente, donde P{displaystyle P} asigna igual probabilidad a todos los gráficos que tienen propiedades especificadas. Se pueden ver como una generalización del modelo Erdős–Rényi G()n,M), cuando la información de condicionamiento no es necesariamente el número de bordes M, pero cualquier otra propiedad gráfica arbitraria P()G){displaystyle {mathcal {}(G)}. En este caso hay muy pocos resultados analíticos disponibles y se requiere simulación para obtener distribuciones empíricas de propiedades promedio.

Historia

El primer uso de un modelo de gráfico aleatorio fue realizado por Helen Hall Jennings y Jacob Moreno en 1938, cuando se utilizó un "sociograma de probabilidad" (un modelo dirigido de Erdős-Rényi) se consideró al estudiar la comparación de la fracción de enlaces recíprocos en los datos de su red con el modelo aleatorio. 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.

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" e independientemente por Gilbert en su artículo "Gráficos aleatorios".