Grafo aleatorio

En matemáticas , el término «grafo aleatorio» se utiliza para referirse a las distribuciones de probabilidad sobre grafos . Los grafos aleatorios pueden describirse simplemente mediante una distribución de probabilidad o mediante un proceso aleatorio que los genera. ^{[ 1 ] [ 2 ]} La teoría de los grafos aleatorios se sitúa en la intersección entre la teoría de grafos y la teoría de la 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 donde 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, el término «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 .

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 posible arista ocurre independientemente con probabilidad 0 < p < 1. La probabilidad de obtener cualquier grafo aleatorio particular con m aristas es${\displaystyle p^{m}(1-p)^{Nm}}$con la notación${\displaystyle N={\tbinom {n}{2}}}$. ^{[ 4 ]}

Un modelo estrechamente relacionado, también llamado modelo de Erdős-Rényi y denotado G ( n , M ), asigna igual probabilidad a todos los grafos con exactamente M aristas. Con 0 ≤ M ≤ N , G ( n , M ) tiene${\displaystyle {\tbinom {N}{M}}}$elementos y cada elemento ocurre con probabilidad${\displaystyle 1/{\tbinom {N}{M}}}$. ^{[ 3 ]} El modelo G ( n , M ) puede verse como una instantánea en un momento particular ( M ) del proceso de grafo aleatorio.${\displaystyle {\tilde {G}}_{n}}$, un proceso estocástico que comienza con n vértices y ninguna arista, y en cada paso agrega una nueva arista elegida uniformemente del conjunto de aristas faltantes.

Si en cambio partimos de un conjunto infinito de vértices, y de nuevo permitimos que cada posible arista ocurra independientemente con una probabilidad de 0 < p < 1, entonces obtenemos un objeto G llamado grafo aleatorio infinito . Excepto en los casos triviales en que p es 0 o 1, dicho G casi con seguridad tiene la siguiente propiedad:

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

Resulta que si el conjunto de vértices es numerable , entonces, salvo isomorfismo , solo existe un único grafo con esta propiedad: el grafo de Rado . Por lo tanto, cualquier grafo aleatorio numerablemente infinito es casi con 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 los grafos no numerables, de los cuales existen 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 a cada vértice un vector real . La probabilidad de que exista una arista uv entre cualesquiera vértices u y v es una función del producto escalar u • v de sus respectivos vectores.

La matriz de probabilidad de red modela grafos aleatorios a través de probabilidades de aristas, que representan la probabilidad${\displaystyle p_{i,j}}$que un borde determinado${\displaystyle e_{i,j}}$Existe durante un período de tiempo determinado. Este modelo es extensible a estructuras de grafos dirigidas y no dirigidas, ponderadas y no ponderadas, y estáticas o dinámicas.

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 grafos regulares aleatorios constituyen un caso especial, con propiedades que pueden diferir de las de los grafos aleatorios en general.

Una vez que tenemos un modelo de grafos aleatorios, cada función en los grafos 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 ]}

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

La teoría de grafos aleatorios estudia las propiedades típicas de los grafos aleatorios, aquellas que se cumplen con alta probabilidad para grafos extraídos de una distribución particular. Por ejemplo, podríamos preguntarnos por un valor dado de${\displaystyle n}$y${\displaystyle p}$¿Cuál es la probabilidad de que...?${\displaystyle G(n,p)}$está conectado . 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${\displaystyle n}$crece enormemente. La teoría de la percolación caracteriza la conectividad de los grafos aleatorios, especialmente los infinitamente grandes.

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

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

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 implica, mediante el lema de regularidad de Szemerédi , la existencia de esa propiedad en casi todos los grafos.

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

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

${\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,${\displaystyle M}$en un grafo aleatorio,${\displaystyle G_{M}}$es lo suficientemente grande como para garantizar que casi todos${\displaystyle G_{M}}$tiene un grado mínimo de al menos 1, entonces casi todos${\displaystyle G_{M}}$está conectado y, si${\displaystyle n}$es uniforme, casi todos${\displaystyle G_{M}}$tiene una coincidencia perfecta. En particular, en el momento en que el último vértice aislado desaparece en casi todos los grafos aleatorios, el grafo se vuelve conectado. ^{[ 3 ]}

Casi todos los procesos gráficos en un número par de vértices con la arista 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 grafo tenga un emparejamiento completo, con excepción de como máximo un vértice.

Por alguna constante${\displaystyle c}$, casi todos los gráficos etiquetados con${\displaystyle n}$vértices y al menos${\displaystyle cn\log(n)}$Las aristas son hamiltonianas . Con una probabilidad que tiende a 1, la arista particular que aumenta el grado mínimo a 2 hace que el grafo sea hamiltoniano.

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 duales de aristas (o grafos de líneas) produce un conjunto de grafos con una distribución de grados casi idéntica, pero con correlaciones de grado y un coeficiente de agrupamiento significativamente mayor. ^{[ 9 ]}

Dado un grafo aleatorio G de orden n con vértice V ( G ) = {1, ..., n }, mediante el algoritmo voraz sobre el número de colores, los vértices pueden colorearse con los colores 1, 2, ... (el vértice 1 se colorea con 1, el vértice 2 se colorea con 1 si no es adyacente al vértice 1, de lo contrario se colorea con 2, etc.). ^{[ 3 ]} El número de coloraciones propias de grafos aleatorios dado un número q de colores, llamado su polinomio cromático , sigue siendo desconocido hasta ahora. El escalado de los 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 ]}

Un árbol aleatorio es un árbol o arborescencia que se forma mediante un proceso estocástico . En una amplia gama 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 el árbol de expansión uniforme , el árbol de expansión mínima aleatorio , el árbol binario aleatorio , el treap , el árbol aleatorio de exploración rápida , el árbol browniano y el bosque aleatorio .

Consideremos un modelo de grafo aleatorio dado definido en el espacio de probabilidad${\displaystyle (\Omega ,{\mathcal {F}},P)}$y dejar${\displaystyle {\mathcal {P}}(G):\Omega \rightarrow R^{m}}$sea ​​una función de valor real que se asigna a cada gráfico en${\displaystyle \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${\displaystyle P}$asigna probabilidad cero a todos los gráficos tales que${\displaystyle {\mathcal {P}}(G)\neq \mathbf {p} }$.

Los casos especiales son los grafos aleatorios uniformes condicionales , donde${\displaystyle P}$Asignan igual probabilidad a todos los grafos que poseen propiedades específicas. Pueden considerarse 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.${\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.

El primer uso de un modelo de grafo aleatorio fue realizado por Helen Hall Jennings y Jacob Moreno en 1938, donde se consideró un "sociograma de azar" (un modelo dirigido de Erdős-Rényi) para 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 grafos 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 ]}

• Condensación de Bose-Einstein: un enfoque de teoría de redes – Modelo en ciencia de redes Páginas que muestran descripciones breves de objetivos de redireccionamiento 
• Método de cavidades : método matemático en física estadística 
• Redes complejas : red con características topológicas no triviales. Páginas que muestran breves descripciones de destinos de redireccionamiento. 
• Evolución de dos fases : proceso que impulsa la autoorganización dentro de sistemas adaptativos complejos. 
• Modelo Erdős-Rényi : dos modelos estrechamente relacionados para generar gráficos aleatorios 
• Modelo de grafo aleatorio exponencial : modelos estadísticos para el análisis de redes. Páginas que muestran breves descripciones de los destinos de redireccionamiento. 
• Teoría de grafos – Área de las matemáticas discretas 
• Redes interdependientes – Subcampo de la ciencia de redes 
• Ciencia de redes – Campo académico 
• Percolación – Filtración de fluidos a través de materiales porosos 
• Teoría de la percolación : teoría matemática sobre el comportamiento de grupos conectados en un grafo aleatorio. 
• Teoría de grafos aleatorios de la gelificación : teoría matemática para los procesos sol-gel. 
• Grafo regular : Grafo en el que cada vértice tiene el mismo número de vecinos. 
• Red libre de escala : red cuya distribución de grados sigue una ley de potencias. Páginas que muestran breves descripciones de los destinos de redireccionamiento. 
• Respuesta semilineal : extensión de la teoría de respuesta lineal a regímenes mesoscópicos. 
• Modelo de bloques estocásticos : un concepto en la ciencia de redes. 
• Comparativa Lancichinetti–Fortunato–Radicchi – Páginas de algoritmos que muestran descripciones breves sin espacios