Grafo aleatorio

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En matemáticas, grafo 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. 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 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 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, gráfico aleatoriose 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 grafo aleatorio se obtiene partiendo de un conjunto de n vértices aislados y sumando 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. 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 en particular con m aristas es $p^{m}(1-p)^{Nm}$ con la notación $N={tbinom {n}{2}}$ .

Un modelo estrechamente relacionado, el modelo Erdős-Rényi denotado G (n, M), asigna la misma probabilidad a todos los gráficos con exactamente M bordes. Con 0 ≤ M ≤ N, G (n, M) tiene ${tbinom {N}{M}}$ elementos y cada elemento ocurre con probabilidad $1/{tbinom {N}{M}}$ . El último modelo se puede ver como una instantánea en un momento particular (M) del proceso de gráfico aleatorio ${ tilde {G}}_{n}$ , que es un proceso estocástico que comienza con n vértices y sin bordes, y en cada paso agrega un nuevo borde elegido uniformemente del conjunto de bordes faltantes.

Si, en cambio, comenzamos con un conjunto infinito de vértices, y nuevamente dejamos que cada posible borde ocurra independientemente 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 cualesquiera $a_{1},ldots,a_{n},b_{1},ldots,b_{m}en V$ , hay un vértice c en V que es adyacente a cada uno de ellos $a_{1},ldots,a_{n}$ y no es adyacente a ninguno de ellos $b_{1},ldots,b_{m}$ .

Resulta que si el conjunto de vértices es contable entonces hay, salvo isomorfismo, solo un único grafo con esta propiedad, a saber, el grafo de Rado. Por lo tanto, cualquier gráfico aleatorio numerable infinito es casi con certeza el gráfico de Rado, que por esta razón a veces se llama simplemente el gráfico aleatorio. Sin embargo, el resultado análogo no es cierto para gráficos incontables, de los cuales hay muchos gráficos (no isomorfos) 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 una arista uv entre cualquier vértice u y v es una 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 borde, que representan la probabilidad $p_{{i, j}}$ de que exista un borde determinado $e_{{i,j}}$ durante un período de tiempo específico. Este modelo es extensible a dirigido y no dirigido; ponderado y no ponderado; 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.

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á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, una propiedad pueda ocurrir.

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.

Propiedades

La teoría de los 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 pedir un valor dado de $norte$ y $pags$ cuál es la probabilidad de que $G(n,p)$ esté conectado. Al estudiar tales 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 a medida que $norte$ crecen mucho. La teoría de la percolación caracteriza la conectividad de grafos aleatorios, especialmente los infinitamente grandes.

La percolación está relacionada con la robustez del gráfico (llamado también red). Dado un gráfico aleatorio de $norte$ nodos y un grado medio $langle krangle$ . A continuación, eliminamos aleatoriamente una fracción $1 p$ de nodos y dejamos solo una fracción $pags$ . Existe un umbral de filtración crítico $p_{c}={tfrac{1}{langle krangle }}$ por debajo del cual la red se fragmenta mientras que por encima $ordenador personal}$ existe un componente conectado gigante.

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

Los gráficos aleatorios son muy utilizados 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 grafos regulares aleatorios, ${ Displaystyle G (n, r-reg)}$ son el conjunto de $r$ grafos -regulares con ${ estilo de visualización r = r (n)}$ tales que $norte$ y $metro$ son los números naturales, ${ estilo de visualización 3 leq r <n}$ , y ${ estilo de visualización rn = 2m}$ es par.

La secuencia de grados de un gráfico $GRAMO$ en $G^{n}$ depende solo del número de aristas en los conjuntos $V_{n}^{(2)}=left{ij: 1leq jleq n,ineq jright}subset V^{(2)},qquad i=1,cdots,n.$

Si los bordes, $METRO$ en un gráfico aleatorio, $G_{M}$ son lo suficientemente grandes como para garantizar que casi todos $G_{M}$ tengan un grado mínimo de al menos 1, entonces casi todos $G_{M}$ están conectados y, si $norte$ son pares, casi todos $G_{M}$ 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.

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

Para alguna constante $C$ , casi todos los gráficos etiquetados con $norte$ vértices y al menos ${displaystyle cnlog(n)}$ bordes 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.

Las propiedades del gráfico aleatorio pueden cambiar o permanecer invariantes bajo las 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 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.

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 se pueden colorear 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.). Hasta el momento se desconoce el número de coloraciones propias de gráficos aleatorios dado un número de q colores, llamado su polinomio cromático. 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 pha sido estudiado empíricamente utilizando un algoritmo basado en la coincidencia de patrones simbólicos.

Árboles aleatorios

Un árbol aleatorio es un árbol o arborescencia que se forma por 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 $(Omega,{mathcal {F}},P)$ y ${displaystyle {mathcal {P}}(G):Omega rightarrow R^{m}}$ sea una función de valor real que asigna a cada gráfico en $Omega$ un vector de m propiedades. Para un fijo ${displaystyle mathbf {p} in R^{m}}$ , los gráficos aleatorios condicionales son modelos en los que la medida de probabilidad $PAGS$ asigna probabilidad cero a todos los gráficos tales que ' ${displaystyle {mathcal {P}}(G)neq mathbf {p} }$ .

Los casos especiales son grafos aleatorios condicionalmente uniformes, donde se $PAGS$ asigna la misma probabilidad a todos los grafos que tienen propiedades específicas. Pueden verse como una generalización del modelo 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 ${displaystyle {mathcal {P}}(G)}$ . En este caso, se dispone de muy pocos resultados analíticos 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 por parte de Helen Hall Jennings y Jacob Moreno en 1938, donde se consideró un "sociograma aleatorio" (un modelo de Erdős-Rényi dirigido) al estudiar la comparación de la fracción de enlaces recíprocos en sus datos de red con el modelo aleatorio.. Otro uso, bajo el nombre de "red aleatoria", fue de Solomonoff y Rapoport en 1951, utilizando un modelo de gráficos dirigidos con grados de salida fijos y adjuntos elegidos al azar 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 "Random graphs".

Contenido relacionado

Más resultados...