Métodos espectrales: modos colectivos de una red

COMPLEXA · Ciencias de la Complejidad y Teoría del Caos
Módulo 20. Procesos colectivos sobre redes y transiciones

191.1. Descomponer un cambio colectivo

Una perturbación local puede propagarse por una red y producir una respuesta que involucra a muchos nodos. Para comprenderla, a veces es útil descomponer el estado en patrones de variación que evolucionan de manera sencilla. En un sistema lineal, esos patrones pueden ser autovectores de la matriz que gobierna la dinámica. Sus autovalores indican cuánto crece, disminuye o cambia de fase cada componente, bajo condiciones que debemos precisar.

El análisis espectral obtiene esos modos a partir de una matriz. La palabra espectro designa el conjunto de sus autovalores. Una red no tiene un espectro único independiente de la representación, ya que la matriz de adyacencia, el laplaciano y la matriz de transición tienen espectros distintos. Cada operador corresponde a una pregunta y a una regla de combinación entre estados vecinos.

En un proceso de difusión, interesa cómo disminuyen diferencias entre lugares conectados. En una propagación linealizada, puede importar si los efectos recibidos superan las pérdidas locales. En una caminata aleatoria, se estudia cómo cambia una distribución de visitas. El mismo soporte de enlaces permite formular los tres procesos, pero sus modos colectivos no deben tratarse como intercambiables.

Los autovectores tampoco son necesariamente grupos de nodos con una función propia. Un modo puede asignar valores positivos a una región y negativos a otra porque describe una diferencia entre sus estados. Su signo global es arbitrario; multiplicar todo el vector por menos uno describe el mismo modo. Interpretar un color de una figura espectral como una propiedad sustantiva exige conocer qué mide la variable y cómo se eligió el operador.

Trabajaremos con una cadena de tres nodos para calcular modos, trayectorias y tiempos de relajación. Después veremos cómo cambian al añadir un enlace, al normalizar por grados y al introducir dirección. El ejemplo mostrará también por qué una trayectoria observada puede ocultar un modo lento y por qué autovalores estables no siempre impiden amplificaciones transitorias.

Los métodos espectrales son útiles cuando reducen una dinámica compleja a relaciones que pueden verificarse. Su valor aumenta si se mantienen explícitos los supuestos de linealidad, las unidades de los pesos y la relación entre el estado matemático y la observación disponible.

191.2. El laplaciano y la desaparición de diferencias

Consideremos una red no dirigida con pesos simétricos no negativos. Sea $W$ su matriz y $D$ la matriz diagonal de fuerzas, con $D_{ii}=\sum_j W_{ij}$. El laplaciano combinatorio es $L=D-W$. Para estados escalares $x_i$, la dinámica difusiva puede escribirse como

Cada enlace contribuye a reducir la diferencia entre sus extremos. Si los estados son concentraciones y todos los nodos tienen la misma capacidad, la simetría conserva la suma de estados. Si las capacidades difieren, la ecuación debe modificarse y la cantidad conservada puede ser una suma ponderada.

La forma cuadrática del laplaciano es

La suma recorre cada arista una vez. Como la matriz es simétrica, todos sus autovalores son reales y existe una base ortogonal de autovectores. La desigualdad anterior garantiza que los autovalores son no negativos. El vector constante tiene autovalor cero porque no hay diferencias que disipar.

Si la red es conexa, ese modo constante es el único modo independiente de autovalor cero. Si hay varias componentes, cada una puede mantener su propio valor constante y la multiplicidad del cero coincide con el número de componentes.

Ordenemos los autovalores como cero, $\lambda_2$ y los restantes en orden creciente. Fiedler (1973) llamó conectividad algebraica al segundo autovalor del laplaciano. Para una red conexa es positivo. En la difusión descrita, determina la tasa más lenta entre los modos no constantes, siempre que ese modo esté presente en la preparación y sea visible en la medición.

La energía cuadrática de las desviaciones respecto del promedio disminuye. Si centramos el estado restando su media, su norma queda acotada por una exponencial cuya tasa depende de $\lambda_2$. Esta afirmación usa la simetría y una norma compatible con la descomposición ortogonal. Más adelante veremos por qué el razonamiento debe revisarse para operadores dirigidos.

Los pesos tienen aquí unidades de tasa cuando el estado no incorpora otras constantes. Multiplicarlos todos por un factor multiplica los autovalores y acelera el reloj en ese mismo factor. Un valor espectral sin unidades o sin definición del operador no permite comparar tiempos entre sistemas.

191.3. Resolver una cadena de tres nodos

Tomemos tres nodos conectados en cadena, con pesos unitarios entre uno y dos y entre dos y tres. El laplaciano es

Sus autovalores son cero, uno y tres. Podemos elegir como autovectores los patrones $(1,1,1)$, $(1,0,-1)$ y $(1,-2,1)$. El primero es una elevación común; el segundo, una diferencia entre extremos; el tercero, una oposición entre el nodo central y ambos extremos. Los patrones son ortogonales y abarcan todos los estados posibles de esta red.

Preparemos el sistema con una unidad en el primer nodo y cero en los demás. La descomposición inicial es

Cada modo no constante decae con su propia tasa, de modo que la solución exacta es

La suma de los tres estados permanece igual a uno y todos convergen a un tercio. El modo de tasa tres desaparece más deprisa. Después, la diferencia entre los extremos domina el resto de la relajación. Esa separación de escalas permite una aproximación de baja dimensión cuando el tiempo es suficientemente grande.

El estado del nodo central es $(1-e^{-3t})/3$. No contiene el modo de tasa uno porque el componente central de su autovector es cero. Si observáramos solo ese nodo, podríamos ajustar una relajación con tasa tres y pasar por alto la escala lenta de la red. En cambio, la diferencia entre el primer y el tercer nodo vale exactamente $e^{-t}$ y permite observarla directamente.

La norma cuadrática del estado centrado es

Los exponentes se duplican porque estamos midiendo amplitudes al cuadrado. Ajustar una tasa sobre energía y compararla sin conversión con una tasa sobre amplitud produciría otro error de interpretación.

El ejemplo reúne tres objetos distintos. El espectro del operador describe modos posibles; la preparación inicial determina cuáles se excitan; la forma de observar decide cuáles resultan visibles. Una trayectoria concreta combina los tres y no permite inferir el operador completo sin información adicional.

191.4. Añadir un enlace y cambiar la escala lenta

Unamos ahora los dos extremos mediante un enlace de peso $\varepsilon\geq0$. El nuevo laplaciano añade una penalización a la diferencia entre ellos. Los mismos tres patrones siguen siendo autovectores por la simetría del problema, pero el modo que opone los extremos cambia de tasa y ahora

El enlace adicional actúa directamente sobre la diferencia entre uno y tres. No altera el otro modo porque sus extremos tienen el mismo valor. La interpretación local del cambio espectral es que una conexión amortigua los patrones que difieren entre sus extremos.

Para pesos entre cero y uno, la conectividad algebraica aumenta desde uno hasta tres. Cuando el peso supera uno, la tasa del modo de extremos sigue creciendo, pero el modo de tasa tres pasa a ser el más lento y limita la brecha espectral. Reforzar indefinidamente un único enlace no acelera de manera ilimitada todas las formas de relajación.

Para generalizar la idea, escribimos el segundo autovalor en forma variacional

Se busca el patrón centrado que disipa menos energía por unidad de norma cuadrática. Si una red contiene dos regiones muy conectadas internamente y débilmente unidas, un estado casi constante dentro de cada región y de signo opuesto entre ellas puede tener poca disipación. El cuello de botella entre ambas regiones produce así un modo lento.

Añadir un enlace de peso positivo, manteniendo los demás, suma una matriz semidefinida positiva; por ello, los autovalores ordenados del laplaciano simétrico no disminuyen. La afirmación vale para ese operador y ese cambio concreto. Si para financiar el nuevo enlace reducimos otros pesos, la comparación deja de ser una simple adición.

Si imponemos un presupuesto total fijo y dividimos todos los pesos por la nueva suma, mezclamos el beneficio estructural con una reducción global de tasas. Una red puede tener rutas adicionales y una relajación más lenta bajo esa redistribución. El resultado no contradice la monotonía anterior, porque se ha cambiado el conjunto completo de pesos.

En aplicaciones, la decisión debe considerar costo, capacidad y modos relevantes. Un enlace que mejora mucho la brecha global puede tener poco efecto sobre una variable observada que apenas proyecta en el modo lento. La utilidad de una intervención espectral depende del objetivo dinámico, además de la estructura.

Podemos cuantificar el efecto de un cuello de botella sin resolver todo el espectro. Imaginemos dos cliques de cinco nodos con pesos internos unitarios y un único enlace entre ellas de peso una décima. Usemos como patrón de prueba el valor uno en la primera clique y menos uno en la segunda. Su media es cero y su norma cuadrática vale diez. Todos los enlaces internos conectan valores iguales y su disipación es nula; la del puente es de cuatro décimas.

El cociente de Rayleigh de ese patrón vale cuatro centésimas. Como el segundo autovalor es el mínimo entre todos los patrones centrados, queda acotado superiormente por ese valor. La escala lenta de relajación es, por tanto, al menos veinticinco unidades temporales bajo las tasas elegidas. El vector de prueba no es necesariamente un autovector exacto, porque en el modo verdadero los nodos del puente pueden diferir ligeramente de sus compañeros.

La comparación muestra cómo grupos internamente rápidos pueden coordinarse lentamente entre sí. Una clique de cinco nodos con pesos unitarios tiene modos internos no constantes de tasa cinco. Al unir dos cliques mediante una conexión débil, aparece una escala colectiva mucho más lenta, la del intercambio entre regiones. El número total de enlaces sigue siendo alto dentro de cada grupo, pero esa abundancia local no elimina la limitación global del puente.

Esta separación de escalas permite una reducción aproximada en la que cada clique se describe por su valor medio una vez amortiguadas las diferencias internas. La aproximación debe comprobarse frente a la dinámica completa, especialmente durante los primeros instantes o cuando el puente deja de ser débil. Una reducción de este tipo conserva el proceso lento de interés y declara qué respuestas rápidas deja fuera.

191.5. Adyacencia, crecimiento y centralidad

La matriz de adyacencia de la cadena de tres nodos tiene autovalores raíz de dos, cero y menos raíz de dos. Su autovector principal puede elegirse proporcional a $(1,\sqrt2,1)$. El nodo central recibe mayor componente porque conecta con ambos extremos. En esta centralidad espectral, el peso de cada nodo es proporcional a la suma de los pesos de sus vecinos.

La interpretación cambia si usamos la adyacencia en una dinámica con producción y pérdida

El modo principal crece cuando $\beta\sqrt2>\delta$ y decae cuando la desigualdad se invierte. El operador describe un mecanismo en el que los vecinos producen actividad en proporción a su estado y cada nodo pierde actividad a una tasa común. No conserva la suma como la difusión laplaciana, porque no resta una salida proporcional al grado de cada nodo.

Por esta diferencia, un autovalor grande puede significar propagación rápida en un modelo y una brecha grande, eliminación rápida de diferencias en otro. Las dos afirmaciones usan operadores y preguntas distintos. Hablar de una red espectralmente inestable sin especificar la ecuación deja indeterminada la conclusión.

Para matrices no negativas, los resultados de Perron–Frobenius permiten identificar un autovalor real dominante bajo condiciones de irreducibilidad. En una red no dirigida y conexa, el autovector principal puede elegirse estrictamente positivo. En una red bipartita aparece también el autovalor opuesto, con igual magnitud. Esa estructura será relevante al estudiar pasos discretos.

El tamaño de un componente principal no mide necesariamente el efecto causal de intervenir sobre ese nodo. La centralidad depende de la matriz completa y de la forma en que sus vecinos contribuyen. Una modificación puede alterar varios modos, restricciones o reglas de comportamiento. Para evaluar el efecto de una intervención hay que incorporar cómo cambia la dinámica y qué resultado se compara.

En algunas redes, gran parte de la norma del autovector principal se concentra en pocos nodos. Un modo dominante así localizado puede describir actividad intensa en una región pequeña sin una expansión macroscópica por toda la población. Un criterio basado solo en el autovalor puede ocultar esa diferencia entre crecimiento local y alcance colectivo.

Los modelos no lineales introducen saturación, agotamiento o cambios de estado. Su linealización cerca de un equilibrio permite estudiar pequeñas perturbaciones, pero la amplitud final depende de esos efectos, además del crecimiento inicial. En los capítulos siguientes usaremos esta distinción al examinar epidemias y transiciones.

191.6. Normalizar por grados cambia el proceso

Una caminata aleatoria sobre la cadena elige uniformemente entre los vecinos disponibles. Su matriz de transición por filas es

La distribución estacionaria es un cuarto, un medio y un cuarto, proporcional a los grados. Sin embargo, desde el primer nodo la distribución alterna entre el centro y los extremos. La cadena es irreducible, pero tiene periodo dos. La existencia de una distribución estacionaria no garantiza convergencia hacia ella desde cualquier preparación.

Los autovalores de la transición son uno, cero y menos uno. El autovalor menos uno corresponde a la alternancia persistente. Si permitimos quedarse en el nodo con probabilidad un medio, la nueva matriz es $(I+P)/2$ y sus autovalores son uno, un medio y cero. La permanencia rompe la periodicidad y las distribuciones convergen.

El laplaciano de caminata aleatoria es $L_{\mathrm{rw}}=I-D^{-1}A$. En una ecuación sobre estados columna, $\dot x=-L_{\mathrm{rw}}x$ hace que cada nodo ajuste su estado hacia el promedio de sus vecinos. Su equilibrio común conserva una media ponderada por grados, distinta de la media uniforme del laplaciano combinatorio.

En la cadena, preparar $(1,0,0)$ produce finalmente un valor común de un cuarto bajo esa ecuación, frente a un tercio en la difusión combinatoria. Ambos resultados son correctos para sus reglas. La primera regla da a cada nodo la misma tasa total de actualización; la segunda da una contribución unitaria a cada enlace, por lo que el nodo central se ajusta con una tasa total mayor.

La matriz simétrica normalizada es

Cuando todos los grados son positivos, es semejante al laplaciano de caminata y comparte sus autovalores. Sus autovectores están escalados de otra manera, por lo que coordenadas, normas y promedios deben convertirse al pasar de un operador a otro.

Los nodos aislados requieren una convención porque la inversa del grado no está definida. Podemos tratarlos como componentes separadas, asignarles permanencia o excluirlos de una tarea específica. Cada opción debe quedar registrada. Una implementación que sustituye automáticamente divisiones problemáticas puede cambiar la interpretación de los modos de frecuencia cero.

La elección entre laplacianos depende de cómo se combinan las influencias. Si cada enlace tiene una tasa física propia, el combinatorio puede ser natural. Si cada nodo dispone de una capacidad total fija que reparte entre vecinos, una normalización puede ser más apropiada.

La normalización puede proceder también de una capacidad física. Si cada nodo es un depósito de volumen conocido, el flujo por un enlace cambia más lentamente la concentración de un depósito grande. La ecuación correcta multiplica la derivada de cada concentración por su volumen. La masa conservada es la suma de volumen por concentración; el equilibrio común se obtiene dividiendo la masa total por el volumen total.

En la cadena, volúmenes uno, dos y uno y una concentración inicial unitaria solo en el primer depósito producen concentración final de un cuarto. Este resultado coincide numéricamente con la normalización por grados porque hemos elegido volúmenes proporcionales a esos grados. La coincidencia del cálculo no identifica el mecanismo, ya que en un caso la normalización expresa almacenamiento físico y en el otro una tasa fija de actualización.

El operador con capacidades desiguales puede escribirse como una matriz no simétrica en coordenadas de concentración, aunque conserve una estructura simétrica mediante un cambio de variables ponderado por los volúmenes. La norma físicamente pertinente también cambia. Por eso conviene revisar el producto interno y las cantidades conservadas antes de interpretar cualquier asimetría matricial como una dinámica dirigida sin equilibrio recíproco.

191.7. Dirección y amplificación transitoria

En una red dirigida, el operador dinámico puede no ser simétrico. Sus autovalores pueden ser complejos y sus autovectores no tienen por qué ser ortogonales. Incluso puede faltar una base completa de autovectores. Estas propiedades cambian la relación entre el espectro y las trayectorias observadas.

Consideremos el sistema lineal de dos variables

La segunda variable alimenta a la primera; aquí una entrada de la matriz dinámica indica influencia de la columna sobre la fila. Esa convención debe distinguirse de una matriz de enlaces que coloque origen en la fila. Los autovalores son menos uno y menos dos, de modo que el origen es asintóticamente estable.

Desde la preparación $(0,1)$, la solución es $x_2(t)=e^{-2t}$ y $x_1(t)=8(e^{-t}-e^{-2t})$. En el tiempo logaritmo de dos, la primera variable alcanza dos y la segunda vale un cuarto. La norma del estado supera dos, aunque inicialmente valía uno y todos los autovalores tienen parte real negativa.

El sistema amplifica transitoriamente antes de decaer. El valor dos es el máximo de la primera componente; no lo hemos identificado con el máximo exacto de una norma del vector completo.

La causa es la estructura no normal del operador, que no conmuta con su traspuesta; sus modos pueden combinarse de manera que una cancelación inicial desaparezca durante la evolución. Trefethen y colaboradores (1993) mostraron la relevancia de esta perspectiva en estabilidad hidrodinámica. El principio matemático también ayuda a interpretar operadores dirigidos, aunque cada aplicación necesite justificar su dinámica.

La estabilidad asintótica sigue siendo válida, porque la amplificación transitoria no cambia el signo de los autovalores ni implica crecimiento indefinido. La amplificación puede, sin embargo, llevar al sistema fuera de la región donde una linealización es adecuada, activar una no linealidad o producir una respuesta grande frente a perturbaciones repetidas.

Para evaluar esa posibilidad se estudian normas del propagador, respuestas a entradas o valores singulares, además del espectro. La dirección de la perturbación y el intervalo temporal considerado forman parte de la pregunta.

191.8. Usar modos para explorar organización

Los modos lentos del laplaciano pueden revelar regiones entre las que se intercambia poco en comparación con sus conexiones internas. Si los nodos de cada región mantienen valores parecidos, el costo cuadrático interno es pequeño. La variación se concentra en los enlaces que cruzan entre regiones, por lo que un corte de poco peso puede producir un autovalor pequeño.

Esta relación motiva métodos de partición espectral. Se calculan uno o varios autovectores y se usan sus coordenadas para proponer grupos. El procedimiento reduce un problema combinatorio a una representación continua, seguida de una regla de corte o agrupamiento. Esa última regla también introduce decisiones y puede ser sensible a nodos situados cerca de una frontera.

El laplaciano combinatorio y el normalizado penalizan los tamaños de grupos de forma diferente. Según el objetivo, uno puede favorecer grupos equilibrados en número de nodos y el otro en volumen de conexiones. Elegir una representación sin examinar esas ponderaciones puede producir grupos que responden principalmente a heterogeneidad de grados.

La modularidad usa otro operador, que resta a la adyacencia una expectativa basada en grados. Newman (2006) desarrolló una formulación espectral para estudiar comunidades a partir de ese contraste. Los autovectores de ese operador describen desviaciones respecto de la referencia elegida. No deben interpretarse como modos difusivos salvo que se establezca una dinámica específica que los use.

Una coordenada espectral puede ser estable como subespacio y, aun así, cambiar como vector individual. Si dos autovalores están muy próximos, pequeñas perturbaciones pueden rotar las direcciones asociadas dentro de su espacio común. Comparar únicamente el signo de un autovector entre dos mediciones puede exagerar un cambio que afecta sobre todo a la elección de base.

También existen redes distintas con el mismo espectro para un operador dado, así que los autovalores no reconstruyen de manera única toda la arquitectura. Con autovectores y correspondencias de nodos hay más información, aunque la observación parcial o el ruido pueden mantener ambigüedad.

La validación debe contrastar la partición con propiedades que interesen al problema, como la permanencia de un flujo, la predicción de enlaces o la coherencia con información independiente. Una separación limpia en el plano de dos autovectores puede ser útil para explorar, pero solo cuenta como evidencia de una frontera funcional si supera esa validación.

191.9. Qué puede inferirse desde una señal observada

Supongamos que registramos una combinación lineal de estados, $y(t)=h^{\mathsf T}x(t)$. Cada modo contribuye según dos factores, que miden cuánto lo excita la preparación y cuánto lo detecta el vector de observación. Si cualquiera de los dos factores es cero, el modo desaparece de esa señal aunque forme parte del operador.

La cadena de tres nodos da un ejemplo exacto. El nodo central no detecta el modo que opone los extremos y una preparación simétrica entre ambos extremos tampoco lo excita. Un experimento que usa únicamente preparaciones y mediciones simétricas no puede estimar su tasa a partir de la relajación, por mucha precisión temporal que tenga.

En sistemas grandes, los factores pueden ser pequeños sin llegar a ser nulos. Un modo lento puede quedar oculto por ruido, por una ventana demasiado corta o por otros modos de mayor amplitud. Ajustar una sola exponencial produce una tasa efectiva que depende del intervalo seleccionado y no siempre coincide con la brecha espectral.

La estimación del operador desde datos añade otra fuente de incertidumbre. Si los enlaces se infieren mediante correlaciones, la matriz obtenida puede reflejar entradas compartidas o ruido de medición. Aplicar una descomposición espectral exacta a esa matriz no elimina la incertidumbre de su origen. Las bandas sobre autovalores y subespacios deben responder a un modelo de datos defendible.

En un sistema lineal estable sometido a ruido, ciertos modos lentos pueden acumular más variabilidad porque disipan perturbaciones con menor rapidez. Sin embargo, la amplitud depende también de cómo entra el ruido y de qué se mide. Observar mayor varianza no identifica necesariamente una reducción de estabilidad, ya que la covarianza de las entradas puede producir cambios semejantes a los del operador.

La agregación temporal puede ocultar modos rápidos y alterar las relaciones aparentes. Muestrear lentamente convierte parte de la dinámica en variación no resuelta. En sistemas con oscilaciones, una frecuencia observada puede confundirse con otra por aliasing. El diseño de medición debe considerar las escalas que se pretende recuperar.

Una inferencia convincente combina preparaciones o perturbaciones diferentes, observaciones suficientes y predicciones reservadas para evaluación. Si un operador estimado explica varias respuestas con los mismos parámetros, la evidencia es mayor que la de un ajuste excelente de una sola señal. La capacidad de distinguir modelos depende del experimento, además del método algebraico.

191.10. Comprobar la dinámica y su discretización

Los modos también permiten revisar una simulación. Para la cadena original, el método de Euler explícito actualiza el estado mediante $x_{t+h}=(I-hL)x_t$. Cada modo se multiplica por uno menos el paso temporal por su autovalor. Para que todos los modos no constantes decaigan en magnitud, el paso debe ser menor que dos tercios.

Ese requisito de estabilidad no garantiza que una concentración inicialmente no negativa permanezca no negativa. En la cadena, las entradas diagonales de la actualización son uno menos el paso en los extremos y uno menos dos veces el paso en el centro. Para que toda la matriz sea no negativa hace falta un paso no mayor que un medio.

Con paso 0,6, la simulación es estable en el sentido modal, pero una preparación concentrada en el nodo central produce estados 0,6, menos 0,2 y 0,6 tras el primer paso. La suma sigue siendo uno, aunque aparece una concentración negativa.

Con paso igual a dos tercios, el modo de autovalor tres cambia de signo sin disminuir su magnitud. Por eso la desigualdad de estabilidad asintótica era estricta. Una trayectoria que oscila en la simulación puede deberse al integrador, sin que el proceso continuo oscile.

El análisis completo debe mantener unidos operador, preparación, observación y método numérico. En el ejemplo sabemos qué cantidad se conserva, qué modos existen y cómo debería evolucionar cada uno. Esa información permite detectar errores antes de interpretar una figura. En redes grandes, comprobaciones equivalentes sobre invariantes y casos simples siguen siendo útiles.

Los métodos espectrales conectan de forma precisa relaciones locales con respuestas colectivas. Su alcance queda definido por la ecuación que se analiza. Si se elige el operador adecuado y se contrastan sus predicciones, el espectro es una herramienta para explicar procesos; si no, queda en una colección de números atribuida indiscriminadamente a la red.

Referencias

• Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298–305. DOI.
• Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582. DOI.
• Trefethen, L. N., Trefethen, A. E., Reddy, S. C., y Driscoll, T. A. (1993). Hydrodynamic stability without eigenvalues. Science, 261(5121), 578–584. DOI.