17.1: Tamaño de Red, Densidad y Percolación
- Page ID
- 115759
Las redes se pueden analizar de varias maneras diferentes. Una forma es analizar sus características estructurales, como el tamaño, la densidad, la topología y las propiedades estadísticas.
Permítanme comenzar primero con las propiedades estructurales más básicas, es decir, el tamaño y la densidad de una red. Estas propiedades son conceptualmente similares a la masa y composición de la materia; solo nos dicen cuántas cosas hay en ella, pero no nos dicen nada sobre cómo se organiza internamente el asunto. No obstante, siguen siendo las características más fundamentales, las cuales son particularmente importantes cuando se quiere comparar múltiples redes. Debe comparar propiedades de dos redes del mismo tamaño y densidad, al igual que los químicos que comparan propiedades del oro y del cobre de la misma masa.
El tamaño de una red se caracteriza por el número de nodos y bordes en ella.
Los objetos Graph de NetworkX tienen funciones dedicadas a medir esas propiedades:
La densidad de una red es la fracción entre 0 y 1 que nos dice qué porción de todos los bordes posibles se realizan realmente en la red. Para una red\(G\) compuesta por\(n\) nodos y\(m\) aristas, la densidad\(ρ(G)\) viene dada por
\[p(G) =\frac{m}{\frac{n(n-1)}{2}} =\frac{2m}{n(n-1)} \label{(17.1)} \]
para una red no dirigida, o
\[p(G)= \frac{m}{n-1}\label{(17/2)} \]
para una red dirigida.
NetworkX tiene una función incorporada para calcular la densidad de la red:
Tenga en cuenta que el tamaño y la densidad de una red no especifican mucho sobre la topología real de la red (es decir, la forma). Hay muchas redes con diferentes topologías que tienen exactamente el mismo tamaño y densidad.
Pero hay algunas cosas que el tamaño y la densidad aún pueden predecir sobre las redes. Un ejemplo de ello es la percolación de red, es decir, si los nodos están o no suficientemente conectados entre sí para que formen un componente gigante que sea visible a escalas macroscópicas. Te puedo mostrar un ejemplo. En el siguiente código, generamos gráficos aleatorios Erd"os-R'enyi hechos de 100 nodos con diferentes probabilidades de conexión:
El resultado se muestra en la Fig. 17.1.1, donde podemos ver claramente una transición de un conjunto de nodos completamente desconectado a una sola red gigante que incluye todos los nodos.
El siguiente código realiza un barrido de parámetros más sistemático de la probabilidad de conexión:
En este código, medimos el tamaño del componente conectado más grande en un gráfico Erd"os-R'enyi con probabilidad de conexión\(p\), mientras aumentamos geométricamente\(p\). El resultado mostrado en la Fig. 17.1.2 indica que una transición de percolación ocurrió alrededor\(p = 10^{−2}\).
Los componentes gigantes son un nombre especial dado a los componentes conectados más grandes que aparecen por encima de este umbral de percolación (se ven en los paneles tercero y cuarto de la Fig. 17.1.1), debido a que sus tamaños están en el mismo orden de magnitud que el tamaño de toda la red. Matemáticamente hablando, se definen como los componentes conectados cuyo tamaño\(s(n)\) tiene la siguiente propiedad
\[\lim_{n \rightarrow {\infty}} \frac{s(n)}{c}\ = \ c \ > \ 0, \label{(17.3)} \]
donde\(n\) está el número de nodos. Este límite iría a cero para todos los demás componentes no gigantes, por lo que a escalas macroscópicas, solo podemos ver componentes gigantes en redes grandes.
Revisar Código 17.4 para generar múltiples gráficos aleatorios para cada uno\(p\), y calcular el tamaño promedio de los componentes conectados más grandes. Luego ejecute el código revisado para tamaños de red más grandes (digamos, 1,000) para obtener una curva más suave.
Podemos calcular el umbral de percolación de red para gráficas aleatorias de la siguiente manera. \(q\)Sea la probabilidad de que un nodo seleccionado aleatoriamente no pertenezca al mayor componente conectado (LCC) de una red. Si\(q < 1\), entonces hay un componente gigante en la red. Para que un nodo seleccionado aleatoriamente se desconecte del LCC, todos sus vecinos también deben estar desconectados del LCC. Por lo tanto, algo tautológicamente
\[q=q^{k}, \label{(17.4)} \]
donde\(k\) está el grado del nodo en cuestión. Pero en general, el grado no\(k\) se determina de manera única en una red aleatoria, por lo que el lado derecho debe ser reescrito como un valor esperado, como
\[q= \sum_{k=0}^{\infty}{P(k)q^{k}}, \label{(17.5)} \]
donde\(P(k)\) está la probabilidad de que el nodo tenga grado\(k\) (llamada distribución de grados; esto se discutirá con más detalle más adelante). En una gráfica aleatoria Erd"os-R'enyi, esta probabilidad se puede calcular mediante la siguiente distribución binomial
\[P(k) = \begin{cases} \binom{n-1}{k}p^{k}(1-p)^{n-1-k} & \text{ for } 0 \leq {k}\leq {n-1}, \label{(17.6)} \\ 0 & \text{ for } k \geq{n}, \end{cases} \]
porque cada nodo tiene vecinos\(n−1\) potenciales y\(k\) fuera de\(n−1\) los vecinos necesita estar conectado al nodo (y el resto necesita ser desconectado de él) para que tenga grado\(k\). Al conectar la Ecuación\ ref {(17.6)} en la Ecuación\ ref {(17.5)}, obtenemos
\[ \begin{align} q= \sum_{k=0}^{n-1}{\binom{n-1}{k}p^{k}(1-p)^{n-1-k}q^{k}} \label{(17.7)} \\ =\sum_{k=0}^{n-1}{\binom{n-1}{k}}(pq)^{k}(1-p)^{1-n-k} \label{(17.8)} \\ =(pq+1-p)^{n-1} \label{(17.9)} \\ =(1+p(q-1))^{n-1}. \label{(17.10)} \end{align} \]
Podemos reescribir esto como
\[q=(1+ \frac{(k)(q-1)}{n}) ^{n-1}, \label{(17.11)} \]
porque el grado promedio\((k)\) de una gráfica Erd"os-R'enyi para una gráfica grande\(n\) viene dada por
\[(k) =np. \label{(17.12)} \]
Ya que\(\lim_{n \rightarrow{\infty}} (1+x/n)^{n} =e^{x}\), la ecuación\ ref {(17.11)} puede simplificarse aún más para grandes\(n\) a
\[q= e^{(k) (q-1)}. \label{(17.13)} \]
Al parecer,\(q = 1\) satisface esta ecuación. Si esta ecuación también tiene otra solución en\(0 < q < 1\), entonces eso significa que es posible un componente gigante en la red. La Figura 17.1.3 muestra las gráficas de\(y = q \) y\(y = e^{(k)(q−1)}\)\(0 < q < 1\) para varios valores de\((k)\).
\[\frac{d}{dq}e^{(k)(q-1)}|_{q=1} =(k)e^{(k)(q-1)}\_{q=1} =(k) >1, \label{(17.14)} \]
es decir, si el grado promedio es mayor que 1, entonces se produce la percolación de la red.
Un componente gigante es un componente conectado cuyo tamaño está en el mismo orden de magnitud que el tamaño de toda la red. La percolación de red es la aparición de tal componente gigante en una gráfica aleatoria, la cual ocurre cuando el grado promedio del nodo está por encima de 1.
Si la Ec. (17.13) tiene una solución en\(q < 1/n\), eso significa que todos los nodos están esencialmente incluidos en el componente gigante, y así la red está hecha de un solo componente conectado. Obtener el umbral de\((k)\) por encima del cual esto ocurre.