Algoritmo de Renormalización para Redes Dinámicas

^[1] 

Algoritmo de Renormalización para Redes Dinámicas

Nicolás Parra Santamaría, USTA

Abstract—A variety of methods can be found for dividing networks into smaller quantities; Within these methods reference is made to spectral divisions, metric inlays, local search; Compared to the dynamic network cabinet. Letting the borders go and come, gives to take into account basic queries about connectivity, which require new tools. This is produced from mainly dynamic graphics; When talking about networks already implemented, are unusually found in fixed set of edges. For a clearer and more concise explanation; Within the web are made hyperlinks that are added and re-removed continuously, as can be evidenced with social networks or any type of graph that may fail. That which leads to inquire into the dynamic networks of multi-agent systems, specifically the behavior of living beings. You could think of the fireflies, they can make their flashes have coordination, the ants when they go on paths using their senses of orientation finding the fastest way to cross them, the synchronization of each living being according to its functions. Like these examples, modeling a system takes into account two extremely indispensable rules: rules of communication that specify which agents "listen" and under what circumstances and rules of action to instruct what to do with the information they acquire.

Key words— Networks, Dinamic, System, pseudorandomness

1. INTRODUCCION

Se pueden encontrar gran variedad de métodos para dividir redes en cantidades más pequeñas; dentro de estos métodos se hace referencia a divisiones espectrales, incrustaciones métricas, búsqueda local; comparado con el armario de redes dinámicas.

Dejar que los bordes vayan y vengan, da para tener en cuenta consultas básicas acerca de conectividad, los cuales requieren de nuevas herramientas.

Esto es producido a partir de gráficos dinámicos principalmente; cuando se habla de redes ya llevado a la práctica, inusualmente se encuentran en conjunto fijo de aristas.

Para una explicación más clara y concisa; dentro de la web se realizan hipervínculos que se añaden y vuelven a eliminar continuamente, como se puede evidenciar con las redes sociales o cualquier tipo de gráfico que pueda llegar a fallar.

Aquello que conlleva a indagar en las redes dinámicas de los sistemas multiagentes, específicamente el comportamiento de los seres vivos. Podría pensarse en las luciérnagas, pueden hacer que sus destellos tengan coordinación, las hormigas cuando van por caminos usando sus sentidos de orientación encontrando la manera más rápida de cruzarlos, la sincronización de cada ser vivo de acuerdo a sus funciones.

Así como estos ejemplos, modelar un sistema, se tiene en cuenta dos reglas sumamente indispensables: reglas de comunicación que especifican qué agentes "escuchan" y bajo qué circunstancias y reglas de acción para instruir sobre qué hacer con la información que adquieren.

1. Analisis de redes dinámicas

El análisis es basado en métodos para el seguimiento de la propagación de la información, esto hace referencia a supervisar la frecuencia con que dos grupos de agentes que se comunican entre sí. Un ejemplo, los agentes pueden dividirse en dos subconjuntos que nunca intercambian información, cada subgrupo está desacoplado del otro y puede analizarse por separado. Dos grupos A y B sin bordes que apuntan de B a A. Dado que la información corre en la dirección inversa de los bordes 1, el grupo B se desacopla y puede analizarse por sí solo, caso contrario con A. Si el sistema B se instala en un ciclo límite, su comportamiento permitirá tratar a este, después de un tiempo adecuado, como un solo agente de bloqueo, comportamiento estático o periódico. De esta manera, el sistema original puede ahora analizarse trabajando primero en B y luego un sistema bidireccional de |A| + 1 agentes (+1 debido a agente de bloqueo). No solo debe reflejar el flujo de información, sino también proceder en línea: en particular, no tener que mirar hacia adelante en el futuro para decidir cómo dividir los agentes en los grupos A y B.  La asignación dinámica de las particiones A y B la línea de tiempo t=0; 1; 2; ... en una secuencia de intervalos consecutivos dentro de los cuales la asignación es invariable en el tiempo. Procesando de esta manera produce recursivamente una descomposición jerárquica de la línea de tiempo, árbol como ((01)(234) ((5(67)(8…)).Los intervalos de tiempo 01234 y 5678, que tienen respectivamente dos y tres hijos, con intervalos 01 y 234 para uno y 5, 67 y 8 para el otro. El procedimiento de análisis sintáctico es un algoritmo de paso de mensajes, como es de señalar la mayoría de los métodos espectrales y los algoritmos de propagación para redes fijas

1. Renormalización temporal

Los sistemas son deterministas, una configuración inicial de los agentes produce una sola órbita. En qué condiciones es la órbita atraída a un ciclo límite. Mientras que la atracción hacia un punto fijo puede ser analizada mirando la órbita de interés y estableciendo una función adecuada de Lyapunov para ella, la periodicidad asintótica no se presta a este tipo de investigación tan fácilmente. Cada órbita da lugar a un árbol de análisis, por lo que el desafío es cómo organizar el conjunto de todos los árboles de análisis posible en una sola estructura: este es el papel del árbol de codificación. Considere el conjunto .El ordenamiento lexicográfico de todas las frases en inglés, como un árbol de codificación infinito cuyos caminos están en biyección con las oraciones. Tales estructuras se conocen en la informática como prefijo, digital, o árboles de la raíz.

En otras palabras, se interpreta el árbol de codificación como uno cuyos nodos son ellos mismos árboles. Lo que hace que el árbol de codificación sea útil para el análisis es que no es meramente una estructura combinatoria sino también geométrica: de hecho, un camino del árbol de codificación corresponde a un conjunto de órbitas cercanas que comparten la misma secuencia de redes. La clave para el análisis es la velocidad a la que se forman nuevas ramas (crecimiento entrópico) y lo delgado que se obtiene a medida que se aleja de la raíz (disipación).En líneas generales, los árboles espesos con ramas gruesas corresponden a sistemas caóticos. Se ha demostrado en un modelo adecuado que una pequeña perturbación aleatoria de la entrada envía a los agentes en un ciclo límite casi con seguridad.

1. 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.

1. 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]

1. 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.

...