更改

In [[mathematics]], the concept of '''graph dynamical systems''' can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties (e.g. the network connectivity) and the global dynamics that result.

In [[mathematics]], the concept of '''graph dynamical systems''' can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties (e.g. the network connectivity) and the global dynamics that result.

In mathematics, the concept of graph dynamical systems can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties (e.g. the network connectivity) and the global dynamics that result.

In mathematics, the concept of graph dynamical systems can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties (e.g. the network connectivity) and the global dynamics that result.

在数学上，图动态系统的概念可以用来捕捉发生在图或网络上的广泛的过程。Gds 数学和计算分析的一个主要主题是将它们的结构特性联系起来(例如:。网络连接)和全球动力学的结果。

在数学上，'''<font color="#ff8000"> 图动态系统'Graph dynamical systems</font>'''的概念可以用来捕捉发生在图或网络上的广泛的过程。Gds 数学和计算分析的一个主要主题是将它们的结构特性联系起来(例如:。网络连接)和全球动力学的结果。

The work on GDSs considers finite graphs and finite state spaces. As such, the research typically involves techniques from, e.g., graph theory, combinatorics, algebra, and dynamical systems rather than differential geometry. In principle, one could define and study GDSs over an infinite graph (e.g. cellular automata or probabilistic cellular automata over <math>\mathbb{Z}^k</math> or interacting particle systems when some randomness is included), as well as GDSs with infinite state space (e.g. <math>\mathbb{R}</math> as in coupled map lattices); see, for example, Wu. In the following, everything is implicitly assumed to be finite unless stated otherwise.

The work on GDSs considers finite graphs and finite state spaces. As such, the research typically involves techniques from, e.g., graph theory, combinatorics, algebra, and dynamical systems rather than differential geometry. In principle, one could define and study GDSs over an infinite graph (e.g. cellular automata or probabilistic cellular automata over <math>\mathbb{Z}^k</math> or interacting particle systems when some randomness is included), as well as GDSs with infinite state space (e.g. <math>\mathbb{R}</math> as in coupled map lattices); see, for example, Wu. In the following, everything is implicitly assumed to be finite unless stated otherwise.

Gdss 的工作是研究有限图和有限状态空间。因此，研究通常涉及技术，如图论，组合学，代数和动力系统，而不是微分几何。原则上，我们可以在一个无限图上定义和研究 gds (例如:。元胞自动机或概率元胞自动机在 math  mathbb { z } ^ k / math 或相互作用的粒子系统(包括一些随机性)上，以及具有无限状态空间的 gds (例如:。在耦合映象格子中的 math  mathbb { r } / math) ; 例如，见 Wu。在下文中，除非另有说明，否则一切都隐含地假定为有限的。

Gdss 的工作是研究有限图和有限状态空间。因此，研究通常涉及到的技术，如[[图论]]，[[组合学]]，[[代数]]和[[动力系统]]，而不是微分几何。原则上，我们可以在一个无限图上定义和研究 gds (例如:。元胞自动机或概率元胞自动机在 math  mathbb { z } ^ k / math 或相互作用的粒子系统(包括一些随机性)上，以及具有无限状态空间的 gds (例如:。在耦合映象格子中的 math  mathbb { r } / math) ; 例如，见 Wu。在下文中，除非另有说明，否则一切都默认为有限。

==Formal definition==

==Formal definition正式定义==

A graph dynamical system is constructed from the following components:

A graph dynamical system is constructed from the following components:

图动态系统是由以下组件构成的:

'''<font color="#ff8000"> 图动态系统'Graph dynamical systems</font>'''是由以下组件构成的:

* A finite ''graph'' ''Y'' with vertex set v[''Y''] = {1,2, ... , n}. Depending on the context the graph can be directed or undirected.

* A finite ''graph'' ''Y'' with vertex set v[''Y''] = {1,2, ... , n}. Depending on the context the graph can be directed or undirected.

 

* A state ''x_v'' for each vertex ''v'' of ''Y'' taken from a finite set ''K''. The ''system state'' is the ''n''-tuple ''x'' = (''x''₁, ''x''₂, ... , ''x_n''), and ''x''[''v''] is the tuple consisting of the states associated to the vertices in the 1-neighborhood of ''v'' in ''Y'' (in some fixed order).

* A state ''x_v'' for each vertex ''v'' of ''Y'' taken from a finite set ''K''. The ''system state'' is the ''n''-tuple ''x'' = (''x''₁, ''x''₂, ... , ''x_n''), and ''x''[''v''] is the tuple consisting of the states associated to the vertices in the 1-neighborhood of ''v'' in ''Y'' (in some fixed order).

 

* A ''vertex function'' ''f_v'' for each vertex ''v''. The vertex function maps the state of vertex ''v'' at time ''t'' to the vertex state at time ''t''&nbsp;+&nbsp;1 based on the states associated to the 1-neighborhood of ''v'' in ''Y''.

* A ''vertex function'' ''f_v'' for each vertex ''v''. The vertex function maps the state of vertex ''v'' at time ''t'' to the vertex state at time ''t''&nbsp;+&nbsp;1 based on the states associated to the 1-neighborhood of ''v'' in ''Y''.

 

* An ''update scheme'' specifying the mechanism by which the mapping of individual vertex states is carried out so as to induce a discrete dynamical system with map ''F'': ''Kⁿ → Kⁿ''.

* An ''update scheme'' specifying the mechanism by which the mapping of individual vertex states is carried out so as to induce a discrete dynamical system with map ''F'': ''Kⁿ → Kⁿ''.

 

</blockquote>

</blockquote>

== Generalized cellular automata (GCA) ==

=='''<font color="#ff8000">Generalized cellular automata (GCA) 广义细胞自动机</font>'''==

If, for example, the update scheme consists of applying the vertex functions synchronously one obtains the class of generalized cellular automata (CA). In this case, the global map F: Kⁿ → Kⁿ is given by

If, for example, the update scheme consists of applying the vertex functions synchronously one obtains the class of generalized cellular automata (CA). In this case, the global map F: Kⁿ → Kⁿ is given by

例如，如果更新方案由同时应用顶点函数组成，则获得广义细胞自动机(CA)类。在这种情况下，整体映射 f: k sup n / sup → k sup n / sup 是由

例如，如果更新方案由同时应用顶点函数组成，则获得'''<font color="#ff8000">Generalized cellular automata (GCA) 广义细胞自动机</font>'''(CA)类。在这种情况下，整体映射 f: k sup n / sup → k sup n / sup 是由

This class is referred to as generalized cellular automata since the classical or standard cellular automata are typically defined and studied over regular graphs or grids, and the vertex functions are typically assumed to be identical.

This class is referred to as generalized cellular automata since the classical or standard cellular automata are typically defined and studied over regular graphs or grids, and the vertex functions are typically assumed to be identical.

== Sequential dynamical systems (SDS) ==

== '''<font color="#ff8000"> Sequential dynamical systems (SDS) 序列动力系统</font>'''==

If the vertex functions are applied asynchronously in the sequence specified by a word w = (w₁, w₂, ... , w_m) or permutation <math>\pi</math> = ( <math>\pi_1</math>, <math>\pi_2,\dots,\pi_n</math>) of v[Y] one obtains the class of Sequential dynamical systems (SDS). In this case it is convenient to introduce the Y-local maps F_i constructed from the vertex functions by

If the vertex functions are applied asynchronously in the sequence specified by a word w = (w₁, w₂, ... , w_m) or permutation <math>\pi</math> = ( <math>\pi_1</math>, <math>\pi_2,\dots,\pi_n</math>) of v[Y] one obtains the class of Sequential dynamical systems (SDS). In this case it is convenient to introduce the Y-local maps F_i constructed from the vertex functions by

如果顶点函数按照 v [ y ]中 w (w 子1 / sub，w 子2 / sub，... ，w 子 m / sub)或置换数学 pi / math (math  pi 1 / math，math  pi 2， dots， pi n / math)指定的序列异步应用，则得到序列动力系统(Sequential dynamic systems，SDS)的类。在这种情况下，可以方便地引入由顶点函数构造的 y 局部映射 f 子 i / 子

如果顶点函数按照 v [ y ]中 w (w 子1 / sub，w 子2 / sub，... ，w 子 m / sub)或置换数学 pi / math (math  pi 1 / math，math  pi 2， dots， pi n / math)指定的序列异步应用，则得到'''<font color="#ff8000"> Sequential dynamical systems (SDS) 序列动力系统</font>''的类。在这种情况下，可以方便地引入由顶点函数构造的 y 局部映射 f 子 i / 子

== Stochastic graph dynamical systems ==

== '''<font color="#ff8000"> Stochastic graph dynamical systems随机图动力系统</font>'''==

==Applications==

==Applications应用==

==See also==

==See also又及==

*[[Chemical reaction network theory]]

*[[Chemical reaction network theory]]

 

*[[Dynamic network analysis]] (a [[social science]] topic)

*[[Dynamic network analysis]] (a [[social science]] topic)

 

*[[Finite state machine]]s

*[[Finite state machine]]s

 

*[[Hopfield net]]works

*[[Hopfield net]]works

 

*[[Kauffman network]]s

*[[Kauffman network]]s

 

*[[Petri net]]s

*[[Petri net]]s

 

==References参考文献==

==References==

==Further reading==

==Further reading延伸阅读==

* {{cite journal |doi=10.1088/0951-7715/22/2/010 |last=Macauley |first=Matthew |author2=Mortveit, Henning S. |year=2009 |title=Cycle equivalence of graph dynamical systems |journal=Nonlinearity |volume=22 |issue=2 |pages=421&ndash;436 |ref=Macauley:09a|arxiv=0802.4412 |bibcode=2009Nonli..22..421M }}

* {{cite journal |doi=10.1088/0951-7715/22/2/010 |last=Macauley |first=Matthew |author2=Mortveit, Henning S. |year=2009 |title=Cycle equivalence of graph dynamical systems |journal=Nonlinearity |volume=22 |issue=2 |pages=421&ndash;436 |ref=Macauley:09a|arxiv=0802.4412 |bibcode=2009Nonli..22..421M }}

==External links==

==External links外部链接==

*[https://web.archive.org/web/20140903062024/http://www.samsi.info/sites/default/files/samsi-05-dec-08.pdf Graph Dynamical Systems – A Mathematical Framework for Interaction-Based Systems, Their Analysis and Simulations by Henning Mortveit]

*[https://web.archive.org/web/20140903062024/http://www.samsi.info/sites/default/files/samsi-05-dec-08.pdf Graph Dynamical Systems – A Mathematical Framework for Interaction-Based Systems, Their Analysis and Simulations by Henning Mortveit]