Sistema dinámico de grafos

En matemáticas , el concepto de sistemas dinámicos de grafos (GDS, por sus siglas en inglés) puede utilizarse para describir una amplia gama de procesos que tienen lugar en grafos o redes. Un tema central en el análisis matemático y computacional de los GDS es relacionar sus propiedades estructurales (por ejemplo, la conectividad de la red) con la dinámica global resultante.

El trabajo sobre GDS considera grafos finitos y espacios de estados finitos. Por lo tanto, la investigación generalmente involucra técnicas de, por ejemplo, teoría de grafos , combinatoria , álgebra y sistemas dinámicos en lugar de geometría diferencial . En principio, se podrían definir y estudiar GDS sobre un grafo infinito (por ejemplo, autómatas celulares o autómatas celulares probabilísticos sobre${\displaystyle \mathbb {Z} ^{k}}$o sistemas de partículas interactuantes cuando se incluye cierta aleatoriedad), así como GDS con espacio de estados infinito (por ejemplo,${\displaystyle \mathbb {R} }$como en las redes de mapas acoplados); véase, por ejemplo, Wu. ^{[ 1 ]} En lo que sigue, se asume implícitamente que todo es finito a menos que se indique lo contrario.

Un sistema dinámico de grafos se construye a partir de los siguientes componentes:

• Un grafo finito Y con conjunto de vértices v[ Y ] = {1,2, ... , n}. Dependiendo del contexto, el grafo puede ser dirigido o no dirigido.
• Un estado x _v para cada vértice v de Y tomado de un conjunto finito K. El estado del sistema es la n -tupla x = ( x ₁ , x ₂ , ... , x _n ), y x [ v ] es la tupla que consiste en los estados asociados a los vértices en el 1-vecindario de v en Y (en algún orden fijo).
• Una función de vértice f _v para cada vértice v . La función de vértice asigna el estado del vértice v en el tiempo t al estado del vértice en el tiempo t  +  1 basándose en los estados asociados al vecindario 1 de v en Y.
• Un esquema de actualización que especifica el mecanismo mediante el cual se lleva a cabo el mapeo de estados de vértice individuales para inducir un sistema dinámico discreto con mapeo F : K ⁿ → K ⁿ .

El espacio de fases asociado a un sistema dinámico con la función F : K ⁿ → K ⁿ es el grafo dirigido finito con conjunto de vértices K ⁿ y aristas dirigidas ( x , F ( x )). La estructura del espacio de fases está determinada por las propiedades del grafo Y , las funciones de vértice ( f _i ) _i , y el esquema de actualización. La investigación en este campo busca inferir propiedades del espacio de fases a partir de la estructura de los constituyentes del sistema. El análisis tiene un carácter local a global.

Si, por ejemplo, el esquema de actualización consiste en aplicar las funciones de vértice de forma síncrona, se obtiene la clase de autómatas celulares generalizados (AC). En este caso, el mapa global F : K ⁿ → K ⁿ viene dado por

${\displaystyle F(x)_{v}=f_{v}(x[v])\;.}$

Esta clase se denomina autómata celular generalizado, ya que los autómatas celulares clásicos o estándar se definen y estudian típicamente sobre grafos o cuadrículas regulares, y se suele asumir que las funciones de los vértices son idénticas.

Ejemplo: Sea Y el grafo circular con vértices {1,2,3,4} y aristas {1,2}, {2,3}, {3,4} y {1,4}, denominado Circ _4. Sea K = {0,1} el espacio de estados para cada vértice y usemos la función nor ₃  : K ³ → K definida por nor ₃ ( x,y,z )  =  (1  + x )(1 + y )(1 + z ) con aritmética módulo 2 para todas las funciones de vértice. Entonces, por ejemplo, el estado del sistema (0,1,0,0) se mapea a (0, 0, 0, 1) usando una actualización síncrona. Todas las transiciones se muestran en el espacio de fases a continuación.        

Si las funciones de vértice se aplican de forma asíncrona en la secuencia especificada por una palabra w = ( w ₁ , w ₂ , ... , w _m ) o permutación${\displaystyle \pi }$= (${\displaystyle \pi _{1}}$,${\displaystyle \pi _{2},\dots,\pi _{n}}$) de v [ Y ] se obtiene la clase de sistemas dinámicos secuenciales (SDS). ^{[ 2 ]} En este caso es conveniente introducir los mapas Y -locales F _i construidos a partir de las funciones de vértice por

${\displaystyle F_{i}(x)=(x_{1},x_{2},\ldots ,x_{i-1},f_{i}(x[i]),x_{i+1},\ldots ,x_{n})\;.}$

El mapa SDS F = [ F _Y , w ]  : K ⁿ → K ⁿ es la composición de funciones.

${\displaystyle [F_{Y},w]=F_{w(m)}\circ F_{w(m-1)}\circ \cdots \circ F_{w(2)}\circ F_{w(1)}\;.}$

Si la secuencia de actualización es una permutación, con frecuencia se habla de una SDS de permutación para enfatizar este punto.

Ejemplo: Sea Y el grafo circular con vértices {1,2,3,4} y aristas {1,2}, {2,3}, {3,4} y {1,4}, denominado Circ _4. Sea K ={0,1} el espacio de estados para cada vértice y usemos la función nor ₃  : K ³ → K definida por nor ₃ ( x,  y,  z ) = (1  + x )(1 + y )(1 + z ) con aritmética módulo 2 para todas las funciones de vértice. Usando la secuencia de actualización (1,2,3,4), el estado del sistema (0, 1, 0, 0) se mapea a (0, 0, 1, 0). Todas las transiciones de estado del sistema para este sistema dinámico secuencial se muestran en el espacio de fases a continuación.           

Desde el punto de vista de las aplicaciones, por ejemplo, resulta interesante considerar el caso en el que uno o más componentes de un GDS contienen elementos estocásticos. Entre las aplicaciones que podrían motivarlo se incluyen procesos que no se comprenden del todo (por ejemplo, la dinámica dentro de una célula) y en los que ciertos aspectos, a efectos prácticos, parecen comportarse según alguna distribución de probabilidad. También existen aplicaciones regidas por principios deterministas cuya descripción es tan compleja o difícil de manejar que conviene considerar aproximaciones probabilísticas.

Cada elemento de un sistema dinámico de grafos puede hacerse estocástico de varias maneras. Por ejemplo, en un sistema dinámico secuencial, la secuencia de actualización puede hacerse estocástica. En cada paso de iteración, se puede elegir la secuencia de actualización w al azar de una distribución dada de secuencias de actualización con probabilidades correspondientes. El espacio de probabilidad correspondiente de las secuencias de actualización induce un espacio de probabilidad de mapas SDS. Un objeto natural de estudio en este sentido es la cadena de Markov en el espacio de estados inducida por esta colección de mapas SDS. Este caso se denomina GDS estocástico de secuencia de actualización y está motivado, por ejemplo, por procesos donde los "eventos" ocurren al azar según ciertas tasas (por ejemplo, reacciones químicas), sincronización en computación paralela/simulaciones de eventos discretos y en paradigmas computacionales descritos más adelante .

Este ejemplo específico con secuencia de actualización estocástica ilustra dos hechos generales para este tipo de sistemas: al pasar a un sistema dinámico de grafos estocásticos, generalmente se llega a (1) un estudio de cadenas de Markov (con una estructura específica regida por los constituyentes del GDS), y (2) las cadenas de Markov resultantes tienden a ser grandes, con un número exponencial de estados. Un objetivo central en el estudio de los GDS estocásticos es poder derivar modelos reducidos.

También se puede considerar el caso en el que las funciones de vértice son estocásticas, es decir, GDS estocásticos de función . Por ejemplo, las redes booleanas aleatorias son ejemplos de GDS estocásticos de función que utilizan un esquema de actualización síncrona y donde el espacio de estados es K = {0, 1}. Los autómatas celulares probabilísticos  finitos (PCA) son otro ejemplo de GDS estocásticos de función. En principio, la clase de sistemas de partículas interactuantes (IPS) abarca PCA finitos e infinitos , pero en la práctica el trabajo sobre IPS se centra principalmente en el caso infinito, ya que esto permite introducir topologías más interesantes en el espacio de estados.

Los sistemas dinámicos de grafos constituyen un marco natural para capturar sistemas distribuidos, como redes biológicas y epidemias en redes sociales, muchos de los cuales se denominan frecuentemente sistemas complejos.

• teoría de la red de reacciones químicas
• Análisis de redes dinámicas (un tema de las ciencias sociales )
• Máquina de estados finitos
• Red Hopfield
• Red de Petri

• Macauley, Matthew; Mortveit, Henning S. (2009). "Equivalencia de ciclos de sistemas dinámicos de grafos". Nonlinearity . 22 (2): 421– 436. arXiv : 0802.4412 . Bibcode : 2009Nonli..22..421M . doi : 10.1088/0951-7715/22/2/010 . S2CID 17978550 . 
• Golubitsky, Martin ; Stewart, Ian (2003). La perspectiva de la simetría . Basilea: Birkhauser. ISBN 0-8176-2171-7.

• Sistemas dinámicos de grafos: un marco matemático para sistemas basados ​​en la interacción, su análisis y simulaciones, por Henning Mortveit.