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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G(n, m)} se define correctamente como una distribución de probabilidad Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P(G)} sobre todos los grafos Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G} , en la cual Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P(G) = 1/\Omega} para grafos simples con Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} vértices y Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle m} aristas, y cero de lo contrario, donde Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G(n, p)} . En Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G(n, p)} no fijamos el número sino la probabilidad de las aristas entre los vértices. De nuevo tenemos Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} vértices, pero ahora colocamos una arista entre cada par de vértices distintos con una probabilidad independiente Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p} estos no son resultados probables, pero podrían ocurrir).

Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G(n, p)} es el ensamblaje de grafos con Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} vértices en el cual cada grafo Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G} aparece con probabilidad

Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P(G) = p^m(1-p)^{\binom{n}{2}-m},}

donde Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle m} es el número de aristas en el grafo.

El modelo Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G(n, p)} para Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p = 1} , cada arista posible en el grafo está presente y el grafo es un clique de Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G(n, p)} , el cual tiene un tamaño constante de Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 1} cuando Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p = 0} y un tamaño extensivo de Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} cuando Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p} aumentando gradualmente, empezando en Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 0} y terminando en Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 1} . Podríamos conjeturar, por ejemplo, que el tamaño del componente más grande aumenta gradualmente con Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p} , volviéndose extensivo solo en el límite donde Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} vértices y Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P(G)} , dada por la ecuación anterior, y por lo tanto la probabilidad total de extraer un grafo con Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle m} aristas de nuestro ensamblaje es

Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle m} es

Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \langle m \rangle = \sum_{m=0}^{\binom{n}{2}} m P(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 (Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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