18.2: Difusión en Redes

Muchos modelos de red dinámica importantes se pueden formular como un sistema dinámico lineal. El primer ejemplo es la ecuación de difusión en una red que discutimos en el Capítulo 16:

\[\frac{dc}{dt} =-\alpha{Lc} \label{(18.5)} \]
Esta es una versión de tiempo continuo, pero también se puede escribir un equivalente de tiempo discreto. Como comentamos antes,\(L = D−A\) es la matriz laplaciana de la red. Es una matriz simétrica en la que todos los componentes diagonales son no negativos (representando grados de nodo) mientras que otros componentes son todos no positivos. Esta matriz tiene algunas propiedades dinámicas interesantes y útiles:

Una matriz laplaciana de una red no dirigida tiene las siguientes propiedades:

1. Al menos uno de sus valores propios es cero.
2. Todos los demás valores propios son cero o positivos.
3. El número de sus valores propios cero corresponde al número de componentes conectados en la red.
4. Si la red está conectada, el vector propio dominante es un vector de homogeneidad\(h = (1 1 ...1)^{T}\) ^a.
5. El valor propio más pequeño distinto de cero se llama la brecha espectral de la red, que determina la rapidez con la que se produce la difusión en la red.

^a Incluso si la red no está conectada, aún se puede tomar el vector de homogeneidad como una de las bases de su propio espacio dominante.

La primera propiedad es fácil de mostrar, pues\(Lh = (D −A)h = d−d = 0\), donde\(d\) esta el vector hecho de grados de nodo. Esto significa que se\(h\) puede tomar como el vector propio que corresponde al valor propio 0. La segunda propiedad proviene del hecho de que la matriz laplaciana es positivo-semidefinita, pues se puede obtener por\(L = M^{T}M\) donde se\(M\) encuentra la matriz de incidencia firmada de la red (no detallada en este libro de texto).

Para entender el resto de las propiedades, debemos considerar cómo interpretar los valores propios de la matriz laplaciana. La matriz de coeficientes reales de la ecuación de difusión es\(−αL\), y sus valores propios son\({−αλ_i}\), donde\({λ_i}\) son\(L\) los valores propios. De acuerdo con las dos primeras propiedades discutidas anteriormente, la matriz de coeficientes de la ecuación tiene al menos un valor propio 0, y todos los valores propios son 0 o negativos. Esto significa que el valor propio cero es en realidad el dominante en este caso, y su correspondiente autovector dominante (\(h\), o autoespacio, si la red no está conectada) nos dirá el estado asintótico de la red.

Revisemos las otras propiedades. La tercera propiedad surge intuitivamente porque, si la red está hecha de múltiples componentes conectados, cada uno de esos componentes se comporta como una red separada y muestra difusión de manera independiente, convergiendo a un valor asintótico diferente, y por lo tanto, el estado asintótico de toda la red debería tener tantos grados de libertad como los componentes conectados. Esto requiere que el espacio propio dominante tenga tantas dimensiones, razón por la cual debería haber tantos 0 de valores propios dominantes degenerados como los componentes conectados en la red. La cuarta propiedad se puede derivar combinando esto con el argumento sobre la propiedad 1 anterior.

Y finalmente, la brecha espectral. Se llama así porque la lista de valores propios de una matriz se llama espectro matricial en matemáticas. La brecha espectral es el valor propio distinto de cero más pequeño de\(L\), que corresponde al valor propio más grande distinto de cero\(−αL\) y, por lo tanto, al modo del estado de la red que muestra la disminución exponencial más lenta a lo largo del tiempo. Si la brecha espectral es cercana a cero, esta desintegración lleva mucho tiempo, lo que resulta en una difusión lenta. O si la brecha espectral está muy por encima de cero, la decadencia ocurre rápidamente, y también lo hace la difusión. En este sentido, la brecha espectral de la matriz laplaciana captura algunos aspectos topológicos de la red, es decir, qué tan bien están conectados los nodos entre sí desde un punto de vista dinámico. La brecha espectral de una gráfica conectada (o, el segundo valor propio más pequeño de una matriz laplaciana en general) se denomina conectividad algebraica de una red.

A continuación se explica cómo obtener una matriz Laplaciana y una brecha espectral en NetworkX:

Entonces, la brecha espectral (= conectividad algebraica en este caso) de la gráfica Karate Club es de aproximadamente 0.4685. Este valor no nos dice mucho sobre la velocidad de difusión en esa red. Tendremos que comparar brechas espectrales entre diferentes topologías de red.

Ejercicio\(\PageIndex{1}\)

Aleatorizar la topología de la gráfica de Karate Club varias veces y medir sus brechas espectrales. Comparar el resultado con el valor original obtenido anteriormente y discutir lo que significa en términos de la velocidad de difusión.

Ejercicio\(\PageIndex{2}\)

Genere las siguientes topologías de red con tamaño y densidad comparables:

• gráfico aleatorio

• gráfico de barra

• gráfico en forma de anillo (es decir, gráfico regular de grado 2)

Mida sus brechas espectrales y vea cómo las topologías afectan cuantitativamente la velocidad de difusión.