Grafo aleatorio

Los grafos aleatorios poseen estructuras típicas de los procesos aleatorios.

En teoría de grafos, un grafo aleatorio es un grafo modelo que, mediante algún tipo de proceso aleatorio, genera grafos que comparten determinadas propiedades y son aleatorios en cuanto al resto de propiedades. El modelo de grafo aleatorio no se define en términos de un solo grafo generado al azar, sino como un ensamblaje de grafos, es decir, una distribución de probabilidad sobre los grafos posibles.

La teoría de los grafos aleatorios cae en la intersección entre la teoría de grafos y la teoría de probabilidades y se fundamenta en el estudio de ciertas propiedades de los grafos aleatorios.

La lógica detrás de los modelos de grafos aleatorios consiste en crear una gran cantidad de grafos que poseen propiedades particulares de interés, como por ejemplo distribuciones de grados específicas, pero que por lo demás son aleatorios. Por ejemplo, se puede crear una gran cantidad de grafos con una determinada distribución de grados, y otra gran cantidad de grafos con una distribución de grados diferente. Explorando las diferencias entre ambos grupos de forma empírica, se puede ver qué características estadísticamente significativas aparecen en un grupo y no en el otro; así se puede ver cómo difieren la estructura y el comportamiento de un grafo en función de su distribución de grados.

Matemáticamente, la idea de los grafos aleatorios está dentro de como enlazar de forma aleatoria un conjunto de $n$ vértices. Para realizar esto se pueden seguir diversas estrategias, cada una de ellas proporciona un modelo de redes (grafos) aleatorios. Uno de los modelos matemáticos más aplicados en la generación de grafos aleatorios es modelo Erdös–Rényi.

En general, un grafo aleatorio es un grafo modelo en el que un conjunto específico de parámetros toma valores fijos, pero el grafo es aleatorio en los demás aspectos.

Los grafos aleatorios son interesantes por derecho propio gracias a la luz que arrojan sobre las propiedades estructurales de los grafos, pero también se han utilizado ampliamente como sustrato para modelos de procesos dinámicos en sistemas reales. Por ejemplo, se usan en el modelado de epidemias.

Uno de los campos de estudio más activo es el de los grafos aleatorios dinámicos en los que se van añadiendo vértices a medida que pasa el tiempo. Estos grafos muestran ciertas propiedades de las redes reales.

Modelo G(n,m)

Uno de los ejemplos más simples de un grafo aleatorio es el grafo en el que fijamos únicamente el número de vértices n y el número de aristas m. Es decir, tomamos n vértices y colocamos m aristas entre ellos al azar. Más precisamente, elegimos m pares de vértices de forma uniformemente aleatoria de entre todos los pares posibles y los conectamos con una arista. Por lo general, se estipula que se trata de un grafo, no de un multigrafo, de manera que la posición de cada arista debe elegirse únicamente entre aquellos pares que sean distintos y que no estén ya conectados. Este modelo se denomina a menudo por su nombre matemático G(n, m).

Otra definición completamente equivalente del modelo consiste en decir que el grafo se crea eligiendo de forma uniformemente aleatoria entre el conjunto de todos los grafos simples que tienen exactamente n vértices y m aristas.

El modelo $G(n,m)$ se define correctamente como una distribución de probabilidad $P(G)$ sobre todos los grafos $G$, en la cual $P(G)=1/\Omega$ para grafos simples con $n$ vértices y $m$ aristas, y cero de lo contrario, donde $\Omega$ es el número total de dichos grafos simples.

Modelo G(n,p)

La mayor parte del trabajo matemático sobre grafos aleatorios se ha llevado a cabo en un modelo ligeramente diferente al G(n,m), que es considerablemente más fácil de manejar. Este modelo se llama $G(n,p)$. En $G(n,p)$ no fijamos el número sino la probabilidad de las aristas entre los vértices. De nuevo tenemos $n$ vértices, pero ahora colocamos una arista entre cada par de vértices distintos con una probabilidad independiente $p$.

En este grafo, el número de aristas no está fijo. De hecho, es posible que el grafo no tenga ninguna arista en absoluto, o que tenga aristas entre cada par de vértices distintos. (Para la mayoría de los valores de $p$ estos no son resultados probables, pero podrían ocurrir).

$G(n,p)$ es el ensamblaje de grafos con $n$ vértices en el cual cada grafo $G$ aparece con probabilidad

$P(G)=p^{m}(1-p)^{{\binom {n}{2}}-m},$

donde $m$ es el número de aristas en el grafo.

El modelo $G(n,p)$ fue estudiado por primera vez por Solomonoff y Rapoport, pero se asocia más estrechamente con los nombres de Paul Erdős y Alfréd Rényi, quienes publicaron una célebre serie de artículos sobre el modelo a finales de la década de 1950 y principios de la de 1960. A veces se hace referencia al modelo como el «modelo de Erdős-Rényi» o el «grafo aleatorio de Erdős-Rényi» en honor a su contribución. También se le llama a veces «grafo aleatorio de Poisson» o «grafo aleatorio de Bernoulli», nombres que hacen referencia a las distribuciones de grados y aristas en el modelo. Y a veces se hace referencia al modelo simplemente como «el» grafo aleatorio; existen muchos modelos de grafos aleatorios, pero $G(n,p)$ es el más fundamental y ampliamente estudiado de ellos, por lo que cuando alguien habla de un grafo aleatorio y no se molesta en mencionar cuál, suele estar pensando en este.

Componentes

Consideremos el grafo aleatorio $G(n,p)$ para $p=0$. En este caso, no hay ninguna arista en el grafo y este se encuentra completamente desconectado. Cada vértice está aislado de los demás. Por tanto, cada vértice es un componente por sí mismo. El grafo tiene $n$ componentes, cada uno de ellos constituido por un único vértice. Por tanto, todos los componentes tienen tamaño 1, de manera que el componente "más grande" también tiene necesariamente tamaño 1. Además, el tamaño del componente más grande es independiente del número de vértices en la red. Si se incrementa n, el tamaño del componente más grande seguirá siendo 1. En este caso se dice que el componente más grande tiene tamaño constante.

En el límite opuesto, cuando $p=1$, cada arista posible en el grafo está presente y el grafo es un clique de $n$ vértices en el sentido técnico de la palabra, lo que significa que cada vértice está conectado directamente con todos los demás. En este caso, todos los vértices están conectados entre sí en un único componente que abarca la red entera. El componente "más grande" tiene necesariamente tamaño n. Esto significa que, si se aumenta el número de vértices n, aumenta proporcionalmente el tamaño del componente más grande. En este caso se dice que el componente más grande tiene tamaño extensivo.

Transición de fase

Consideremos el componente más grande del grafo aleatorio $G(n,p)$, el cual tiene un tamaño constante de $1$ cuando $p=0$ y un tamaño extensivo de $n$ cuando $p=1$.

Una pregunta que cabe hacerse es cómo ocurre la transición entre estos dos extremos si construimos grafos aleatorios con valores de $p$ aumentando gradualmente, empezando en $0$ y terminando en $1$. Podríamos conjeturar, por ejemplo, que el tamaño del componente más grande aumenta gradualmente con $p$, volviéndose extensivo solo en el límite donde $p=1$. En realidad, sin embargo, el tamaño del componente más grande experimenta un cambio repentino, o transición de fase, de un tamaño constante a un tamaño extensivo en un valor especial y particular de $p$.

Número de aristas esperado

El número de aristas en el modelo no está fijo, pero podemos calcular su valor esperado de la siguiente manera. El número de grafos con exactamente $n$ vértices y $m$ aristas es igual al número de formas de elegir las posiciones de las aristas a partir de los pares de vértices distintos. Cada uno de estos grafos aparece con la misma probabilidad $P(G)$, dada por la ecuación anterior, y por lo tanto la probabilidad total de extraer un grafo con $m$ aristas de nuestro ensamblaje es

$P(m)={\binom {\binom {n}{2}}{m}}p^{m}(1-p)^{{\binom {n}{2}}-m}$,

lo que es exactamente la distribución binomial estándar. Entonces, el valor esperado de $m$ es

$\langle m\rangle =\sum _{m=0}^{\binom {n}{2}}mP(m)={\binom {n}{2}}p.$

Este resultado no es ninguna sorpresa. El número de aristas esperado entre cualquier par individual de vértices es simplemente igual a la probabilidad de una arista entre esos mismos vértices ($p$), y la ecuación por lo tanto dice simplemente que el número de aristas esperado en el grafo es igual al número esperado $p$ entre cualquier par de vértices, multiplicado por el número de pares.

Teoremas

Algunos teoremas se deducen del modelo, por ejemplo, si G(n; p) es un grafo aleatorio con n vértices donde cada enlace tiene una posibilidad p de existir:

Teorema 1

Dado un G(n, p) con un valor p constante e independiente de n, entonces el grafo seguro que posee casi seguro un diámetro igual a 2.

Teorema 2

Para un grafo G(n, p) aleatorio se establece que $\textstyle p=c{\frac {\log n}{n}}$. Si c > 1 entonces casi todos los grafos no poseen vértices aislados y si c < 1 casi todos los grafos tienen al menos un vértice aislado.

Aplicaciones

Una de las ramas más estudiadas en el área de las redes aleatorias es el de la teoría de la percolación (nivel de percolación) relacionado con el estudio de la fiabilidad en las redes de comunicación. Un campo de estudio inicial fue el de redes sociales, estudios sobre la topología de redes evolutivas como puede ser internet, etc. Se ha visto que algunas de las redes actuales crecen según modelos predefinidos en su distribuciones de grado, como puede ser la redes libres de escala.

Referencias

• Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press
• Christine Nickel, Random Dot Product Graphs: A Model for Social Networks, Ph.D. Thesis, The Johns Hopkins University, 2007.
• Newman, M. E. J. (2010). «Chapter 12. Random Graphs». Networks: An Introduction. Oxford University Press. 

Enlaces externos

• Networks and Emergence in Complex Systems - Barcelona School of Economics