En matemáticas , el concepto de sistemas dinámicos de gráficos se puede utilizar para capturar una amplia gama de procesos que tienen lugar en gráficos o redes. Un tema importante en el análisis matemático y computacional de los GDS es relacionar sus propiedades estructurales (por ejemplo, la conectividad de la red) y la dinámica global resultante.
El trabajo en GDS considera gráficos finitos y espacios de estados finitos. Como tal, 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, uno podría definir y estudiar GDS sobre un gráfico infinito (por ejemplo, autómatas celulares o autómatas celulares probabilísticos sobreo sistemas de partículas que interactúan cuando se incluye algo de aleatoriedad), así como GDS con espacio de estado infinito (p. ej.como en las celosías de mapas acopladas); ver, por ejemplo, Wu. [1] A continuación, se asume implícitamente que todo es finito a menos que se indique lo contrario.
Definicion formal
Un sistema dinámico de gráficos se construye a partir de los siguientes componentes:
- Un gráfico finito Y con vértice establecido v [ Y ] = {1,2, ..., n}. Dependiendo del contexto, el gráfico puede estar 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 1 , x 2 , ..., x n ), y x [ v ] es la tupla que consta de los estados asociados a los vértices en la vecindad 1 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 vértice asigna el estado de vértice v en el momento t al estado vértice en el tiempo t en base a los estados asociados a la 1-barrio de + 1 V en Y .
- Un esquema de actualización que especifica el mecanismo por el cual se lleva a cabo el mapeo de estados de vértice individuales para inducir un sistema dinámico discreto con el mapa F : K n → K n .
El espacio de fase asociado a un sistema dinámico con mapa F : K n → K n es el gráfico dirigido finito con el conjunto de vértices K n y aristas dirigidas ( x , F ( x )). La estructura del espacio de fase se rige por las propiedades del gráfico Y , las funciones de vértice ( f i ) i y el esquema de actualización. La investigación en esta área busca inferir propiedades del espacio de fase basadas en la estructura de los constituyentes del sistema. El análisis tiene un carácter de local a global.
Autómatas celulares generalizados (GCA)
Si, por ejemplo, el esquema de actualización consiste en aplicar las funciones de vértice sincrónicamente se obtiene la clase de autómatas celulares generalizados (CA). En este caso, el mapa global F : K n → K n viene dado por
Esta clase se conoce como generalizada autómatas celulares desde los clásicos o estándar autómatas celulares se definen típicamente y estudiados durante grafo regular o rejillas, y las funciones de vértices están típicamente supone que ser idénticos.
Ejemplo: Sea Y el gráfico circular en los vértices {1,2,3,4} con aristas {1,2}, {2,3}, {3,4} y {1,4}, denotado Circ 4 . Sea K = {0,1} el espacio de estados para cada vértice y use la función nor 3 : K 3 → K definida por nor 3 ( x, y, z ) = (1 + x ) (1 + y ) (1 + z ) con módulo aritmético 2 para todas las funciones de vértice. Entonces, por ejemplo, el estado del sistema (0, 1, 0, 0) se asigna a (0, 0, 0, 1) mediante una actualización sincrónica. Todas las transiciones se muestran en el espacio de fase a continuación.
Sistemas dinámicos secuenciales (SDS)
Si las funciones de vértice se aplican de forma asincrónica en la secuencia especificada por una palabra w = ( w 1 , w 2 , ..., w m ) o permutación = ( , ) de v [ Y ] se obtiene la clase de Sistemas dinámicos secuenciales (SDS). [2] En este caso es conveniente introducir los mapas locales Y- F i construidos a partir de las funciones de vértice por
El mapa SDS F = [ F Y , w ]: K n → K n es la composición de la función
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 gráfico circular en los vértices {1,2,3,4} con aristas {1,2}, {2,3}, {3,4} y {1,4}, denotado Circ 4 . Sea K = {0,1} el espacio de estados para cada vértice y use la función nor 3 : K 3 → K definida por nor 3 ( x, y, z ) = (1 + x ) (1 + y ) (1 + z ) con módulo aritmético 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 asigna a (0, 0, 1, 0). Todas las transiciones de estado del sistema para este sistema dinámico secuencial se muestran en el espacio de fase a continuación.
Sistemas dinámicos de gráficos estocásticos
Por ejemplo, desde el punto de vista de las aplicaciones, es interesante considerar el caso en el que uno o más de los componentes de un GDS contienen elementos estocásticos. Las aplicaciones motivadoras podrían incluir procesos que no se comprenden completamente (por ejemplo, la dinámica dentro de una celda) y donde ciertos aspectos para todos los propósitos prácticos parecen comportarse de acuerdo con alguna distribución de probabilidad. También hay aplicaciones que se rigen por principios deterministas cuya descripción es tan compleja o difícil de manejar que tiene sentido considerar aproximaciones probabilísticas.
Cada elemento de un sistema dinámico de gráficos puede hacerse estocástico de varias formas. 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 las probabilidades correspondientes. El espacio de probabilidad coincidente de las secuencias de actualización induce un espacio de probabilidad de mapas SDS. Un objeto natural para estudiar a este respecto 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 en los que los "eventos" ocurren aleatoriamente de acuerdo con ciertas velocidades (por ejemplo, reacciones químicas), sincronización en simulaciones de computación / eventos discretos en paralelo y en paradigmas computacionales que se describen más adelante. .
Este ejemplo específico con secuencia de actualización estocástica ilustra dos hechos generales para tales sistemas: cuando se pasa a un sistema dinámico de gráficos estocásticos, generalmente se lleva a (1) un estudio de las cadenas de Markov (con una estructura específica gobernada por los constituyentes del GDS), y (2) las cadenas de Markov resultantes tienden a ser grandes y tienen un número exponencial de estados. Un objetivo central en el estudio de GDS estocástico 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, la función estocástica GDS . Por ejemplo, las redes booleanas aleatorias son ejemplos de función GDS estocástica que usa un esquema de actualización sincrónico y donde el espacio de estado es K = {0, 1}. Los autómatas celulares probabilísticos finitos (PCA) son otro ejemplo de función estocástica GDS. En principio, la clase de sistemas de partículas interactivas (IPS) cubre PCA finito e infinito , pero en la práctica el trabajo sobre IPS se ocupa en gran medida del caso infinito, ya que esto permite introducir topologías más interesantes en el espacio de estados.
Aplicaciones
Los sistemas gráficos dinámicos constituyen un marco natural para capturar sistemas distribuidos como redes biológicas y epidemias a través de redes sociales, muchos de los cuales se denominan con frecuencia sistemas complejos.
Ver también
Referencias
- ^ Wu, Chai Wah (2005). "Sincronización en redes de sistemas dinámicos no lineales acoplados mediante grafo dirigido". No linealidad . 18 (3): 1057–1064. Código Bibliográfico : 2005Nonli..18.1057W . doi : 10.1088 / 0951-7715 / 18/3/007 .
- ^ Mortveit, Henning S .; Reidys, Christian M. (2008). Una introducción a los sistemas dinámicos secuenciales . Universitext. Nueva York: Springer Verlag . ISBN 978-0-387-30654-4.
Otras lecturas
- Macauley, Matthew; Mortveit, Henning S. (2009). "Ciclo de equivalencia de sistemas gráficos dinámicos". No linealidad . 22 (2): 421–436. arXiv : 0802.4412 . Código de Bibliografía : 2009Nonli..22..421M . doi : 10.1088 / 0951-7715 / 22/2/010 .
- Golubitsky, Martin ; Stewart, Ian (2003). La perspectiva de la simetría . Basilea: Birkhauser. ISBN 0-8176-2171-7.