グラフダイナミカルシステム

数学では、グラフダイナミカルシステム は、グラフやネットワーク上で起こる様々なプロセスを捉えるために使用することができる。GDSの数学的および計算機的解析の主要なテーマは、その構造的特性（例えば、ネットワークの接続性）とその結果生じるグローバルダイナミクスを関連付けることである。

GDSの研究では、有限グラフと有限状態空間が扱われる。そのため、微分幾何学よりも、例えばグラフ理論、組合せ論、代数、力学系などの技術が研究対象としてよく用いられる。 原理的には、無限グラフ上のGDS（例えば、$\mathbb {Z} ^{k}$上のセルオートマトンや確率的セルオートマトン、ランダム性を含む場合の相互作用粒子系）、および無限状態空間を持つGDS（例えば、連写格子における$\mathbb {R}$）を定義し研究することが可能である。例えば, Wu を参照せよ。以下では、特に断りのない限り、すべてが有限であると暗黙のうちに仮定している。

形式的定義

グラフダイナミカルシステムは以下の構成要素から構成される。

• 節点の集合v[Y] = {1,2, ... , n}をもつある有限グラフ Y. 方向ありかなしかという文脈に依存。
• 有限集合Kから得たYのそれぞれの節点vに対するある状態x_v。系の状態とはn-タプル x = (x₁, x₂, ... , x_n), であり x[v] はYにおいてvの1近傍にある頂点に関連する状態からなるタプルである（ある一定の順序で）。
• 節点関数とはf_vである. 節点関数はYにおけるvの1近傍に関連する状態に基づいて、tにおけるvの状態をt + 1にマッピングする。
• 個々の頂点の状態の写像を行うメカニズムを指定した更新スキームが離散力学系を引き起こすようなFとは、F: Kⁿ → Kⁿ である。

位相空間は節点集合Kⁿと方向付き辺(x, F(x))からなる写像F: Kⁿ → Kⁿを持つダイナミカルシステムに関連付けられる。位相空間の構造はグラフY、vertex functions (f_i)_i、更新スキームによって支配される。この分野の研究は、システムの構成要素の構造に基づいて位相空間の特性を推測しようとするものである。解析は局所から大域へという性格を持つ。

一般化セルオートマトン(GCA)

例えば、更新方式が頂点関数を同期的に適用するものであれば、GCAのクラスが得られる。この場合、グローバル写像F: Kⁿ → Kⁿ は以下で与えられる。

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

このクラスは、古典的あるいは標準的なセル・オートマトンが正則グラフあるいは格子上で定義・研究され、頂点関数が同一であることが一般に仮定されているので、一般化セルオートマトンと呼ばれる。

シーケンシャルダイナミカルシステム (SDS)

頂点関数が次の語で指定された順序 w = (w₁, w₂, ... , w_m) で非同期に適用されるか順列 $\pi$ = ( $\pi _{1}$, $\pi _{2},\dots ,\pi _{n}$) of v[Y] はSDSのクラスを得る。 この場合、頂点関数から構成されるY-局所写像F_iの導入は便利であり、以下で与えられる。

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

SDS写像 F = [F_Y , w] : Kⁿ → Kⁿ は写像の合成

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

である。もし更新シーケンスが順列なら、permutation SDSと呼ばれる。

確率的グラフダイナミカルシステム

例えば、アプリケーションの観点からは、GDS の構成要素の 1 つ以上が確率的要素を含む場合を考 えることは興味深いことである。例えば、細胞内のダイナミクスのような完全に解明されていないプロセスで、ある側面が確率分布にしたがって動作しているようなアプリケーションである。また、決定論的原理によって支配されるアプリケーションで、その記述が非常に複雑であったり、扱いにくいため、確率的な近似を考慮することが理にかなっている場合がある。

グラフダイナミカルシステムの各要素は、いくつかの方法で確率的にすることができる。例えば、逐次動的システムにおいては、更新順序を確率的にすることができる。各反復ステップにおいて、更新順序 w を、対応する確率を持つ更新順序の与えられた分布からランダムに選択することができる。更新シーケンスのマッチング確率空間は、SDS写像の確率空間を生成する。このSDS写像の集まりが引き起こす状態空間上のマルコフ連鎖が自然な研究対象である。この場合、update sequence stochastic GDS と呼ばれ、例えば、「イベント」がある割合でランダムに発生する過程（例えば化学反応）、並列計算・離散イベントシミュレーションにおける同期、後述の計算パラダイムの動機付けとなる。.

確率的グラフダイナミカルシステムに移行すると、一般に、(1) マルコフ連鎖の研究（GDSの構成要素に支配される特定の構造を持つ）に導かれること、(2) 結果として得られるマルコフ連鎖は指数関数的に状態数が増えて大きくなる傾向があること、の2点がこの種の系における一般的事実として示されている。確率的GDSの研究の中心的な目標は、縮小モデルを導出できるようにすることである。

また、頂点関数が確率的である場合についても考えることができる。 例: function stochastic GDS. 例えば、ランダムブールネットワークは、同期更新方式を用いた関数型確率的GDSの例である。ただし、状態空間はK = {0, 1}。有限確率セルオートマトン(PCA)は関数逐次GDSの別の例である。原則として、Interacting particle systems(IPS)は有限と無限の確率セルオートマトンをカバーするが、実際には、IPSの研究は、状態空間により興味深いトポロジーを導入することができるため、主に無限の場合に関係している。

応用

グラフダイナミカルシステムは、生物ネットワークや社会ネットワーク上の伝染病など、複雑系と呼ばれる分散システムを捉えるための自然なフレームワークを構成している。

関連項目

• Chemical reaction network theory
• Dynamic network analysis (a social science topic)
• Finite state machines
• Hopfield networks
• Kauffman networks
• Petri nets

Further reading

• Macauley, Matthew; Mortveit, Henning S. (2009). “Cycle equivalence of graph dynamical systems”. Nonlinearity 22 (2): 421–436. arXiv:0802.4412. Bibcode: 2009Nonli..22..421M. doi:10.1088/0951-7715/22/2/010. 
• Golubitsky, Martin; Stewart, Ian (2003). The Symmetry Perspective. Basel: Birkhauser. ISBN 0-8176-2171-7 

外部リンク

• Graph Dynamical Systems – A Mathematical Framework for Interaction-Based Systems, Their Analysis and Simulations by Henning Mortveit