Algoritmo de Renormalización para Redes Dinámicas

...

- El modelo

Inspirado en el clásico Hegselmann-Krause (HK) modelo de dinámica de opinión. Parte de: fijar un parámetro real r> 0 y inicializar un agente en la línea real R.[pic 1]del agente ise, convierte [pic 2]en la siguiente [pic 3]. Las simulaciones numéricas sugieren convergencia rápida. El tiempo de relajación aún no se ha fijado, se sabe que, dentro del tiempo polinomial, los agentes terminan congelados en punto único clústeres al menos r alejados unos de otros.

- Sistemas generalizados HK

Hay tres maneras naturales de extender el modelo original HK. Uno de ellos es levantar los agentes de dimensión superior en lugar de confinarlos a la línea real. Independientemente de la dimensión, los agentes aún convergerán hacia una configuración fija en tiempo polinomial; Otra modificación es reemplazar la regla de actualización con un centro de masa ponderada. Considere dos agentes a una distancia menor que r que se mueven hacia cada uno hacia otro tercio del camino en cada paso.[pic 4]y [pic 5].En el espacio de fase R2, cualquier órbita es atraída exponencialmente rápido a la línea x1= x2; El tercer tipo de extensión es redefinir lo que significa ser un "vecino". Un cambio tan simple como permitir un umbral diferente ri para cada agente i produce una dinámica que aún no está resuelta. Aunque busca mucho diferente a simple vista, esto es una ilusión: las dos formulaciones son en realidad equivalentes (módulo un ajuste en el número de agentes).

Un lin-DNF es un conjunto de restricciones lineales expresadas como una disyunción de conjunciones, i.e., [pic 6]donde cada Pi es de la forma [pic 7]y cada [pic 8]es un medio espacio[pic 9](or [pic 10]) donde [pic 11]se define el gráfico de comunicación como [pic 12]asociando un nodo a cada agente. Los bordes del gráfico de n-nodos[pic 13]dependen de [pic 14]para cada par [pic 15]elegimos un lin-DNF[pic 16]y declaran (i,j) para ser un borde [pic 17]si [pic 18]es verdadero. Una extensión natural de los sistemas HK es proporcionada por la regla de actualización: para i =1,......,n, [pic 19]el sistema HK original se pone en forma lin-DNF muy simplemente fijando[pic 20]como [pic 21]

- Sistemas de influencia difusiva

La definición de un sistema de influencia difusiva es idéntica a la de un sistema HK, con la única diferencia procedente de la red de comunicación, específicamente el criterio utilizado para incluir un par (i,j) como un borde [pic 22]se equipa el par con su propio predicado de primer orden[pic 23]y hace (i,j) un borde de[pic 24]si y sólo si [pic 25]es verdadero. ¿Es necesaria la teoría de primer orden de los reales? la respuesta es sí.

Prácticamente cualquier regla de selección de borde es aceptable, la cumple el objetivo principal del modelo, que es permitir los agentes a tener sus propias reglas de comunicación distintas: de hecho, cualquiera de los dos agentes puede utilizar criterios elegir a sus vecinos.

- Equivalencia de los modelos

En el lenguaje de la lógica de primer orden, los sistemas de influencia difusiva parecen muy alejados de la formulación lin-DNF de los sistemas HK generalizados. Cualquier sistema de influencia difusiva puede ser puesto en forma lin-DNF después de una transformación adecuada. Esto implica una serie de pasos incluyendo la eliminación del cuantificador, la linealización, tensoring, la adición de nuevos agentes, etc. Los polinomios de grado arbitrario puedan ser sustituidos por los lineales, pero esto es posible gracias a la naturaleza "convexa"; forman un arreglo cuyas células dimensionales c, las piezas de continuidad de f son cada una.

[pic 26]

Un mapa f para n=2. Nótese que la pieza de continuidad c se mapea continuamente pero f(c) no. Este tipo de fragmentación hace que la dinámica sea difícil de analizar.

Se asume una diagonal positiva para evitar periodicidades espurias de poca significación matemática; se define P(x) como matriz de identidad para cualquier x en una discontinuidad o en la límite del cubo unitario. Una forma de resumir este documento es la suposición de que los sistemas están acoplados localmente, lo que significa que cada fi depende sólo de xi, xj y no sobre los otros agentes.

- Nueva marca de renormalización

La mayoría de los regímenes dinámicos pueden observarse en dimensiones bajas (por ejemplo, atracción de punto fijo, periodicidad. La idea básica es reescalar un sistema manteniendo su dinámica. En nuestro caso, la escala es con respecto al tiempo y el número de agentes. Renormalizar un sistema de influencia es producir otro con menos agentes y un comportamiento similar a una versión del original. Si el gráfico de comunicación fue fijo, las técnicas de agrupación gráfica podrían sugerir una forma de hacerlo: los agentes que interactúan con sus vecinos en una cuadrícula, por ejemplo, pueden agruparse en sub-cuadrículas, de modo que un [pic 27]red de n agentes se puede renormalizar como un[pic 28]cuadrícula de "agentes de bloque" que consiste en cuatro agentes cada uno. Esta forma de renormalización de bloques de spin, introducida por Kadanoff para el modelo de Ising, sólo funciona si la interacción entre los agentes de bloque se puede entender razonablemente bien sin tener que rastrear el comportamiento preciso de sus agentes constituyentes, se acostumbra a ver el proceso como un sistema dinámico que mapea un Ising modelo a otro, más simple. Se revisa el método aquí y se muestra cómo reemplazar una suposición de temporización determinada por una heurística de posición general bajo la cual se puede demostrar que la región crítica es de medida cero. La renormalización algorítmica de las redes dinámicas es una idea general y poderosa que probablemente será útil en otros lugares.

- Escalas de tiempo mixtas

Se ha demostrado que los sistemas de influencia difusiva abarcan toda la gama de modos dinámicos, desde la atracción de puntos fijos hasta el caos. Los ciclos de largo límite con grandes cuencas de atracción pueden ser fabricados también: siendo como órbitas periódicas extremadamente largas robustas bajo perturbación. El período es una torre-de-dos de altura proporcional al número de agentes. Este tipo de comportamiento puede ser patológico pero afecta a un fenómeno en el corazón de los sistemas de influencia: la mezcla de escalas de tiempo. Un agente comienza con una cantidad ilimitada de información (codificada en su posición inicial) pero, una