グラフ力学システム

数学では、グラフ動的システムの概念は、グラフやネットワーク上で発生するさまざまなプロセスを捉えるために使用できます。GDS の数学的および計算的分析における主要なテーマは、その構造特性 (ネットワークの接続性など) と、その結果生じるグローバル ダイナミクスを関連付けることです。

GDS に関する研究では、有限グラフと有限状態空間が考慮されています。そのため、研究には通常、微分幾何学ではなく、グラフ理論、組合せ論、代数学、力学システムなどの手法が含まれます。原理的には、無限グラフ上の GDS (セルオートマトン、またはランダム性が含まれる相互作用粒子システム上の確率的セルオートマトンなど) や、無限状態空間を持つ GDS (結合写像格子など) を定義して研究することができます。たとえば、Wu を参照してください。^[1]以下では、特に明記しない限り、すべてが暗黙的に有限であると想定されています。 ${\displaystyle \mathbb {Z} ^{k}}$${\displaystyle \mathbb {R} }$

グラフ動的システムは、次のコンポーネントから構成されます。

• 頂点集合 v[ Y ] = {1,2, ... , n} を持つ有限グラフ Y。コンテキストに応じて、グラフは有向または無向になります。
• 有限集合Kから取られたYの各頂点vの状態x _v。システムの状態はn組x = ( x ₁ , x ₂ , ... , x _n ) であり、x [ v ] はYのvの 1 近傍の頂点に関連付けられた状態(一定の順序)で構成される組です。
• 各頂点vに対する頂点関数 f _v。頂点関数は、Yにおけるv の 1 近傍に関連付けられた状態に基づいて、時刻tにおける頂点vの状態を時刻t + 1 における頂点状態にマッピングします。
• 個々の頂点状態のマッピングが実行され、マップF : K ⁿ → K ⁿを持つ離散動的システムが誘導されるメカニズムを指定する更新スキーム。

マップF : K ⁿ → K ⁿを持つ動的システムに関連付けられた位相空間は、頂点集合K ⁿと有向辺 ( x、F ( x ) )を持つ有限有向グラフです。位相空間の構造は、グラフY、頂点関数 ( f _i ) _i、および更新スキームの特性によって決まります。この分野の研究では、システム構成要素の構造に基づいて位相空間の特性を推測します。分析は、ローカルからグローバルまでの特性を持っています。

例えば、更新スキームが頂点関数を同期的に適用することから構成される場合、一般化セルオートマトン（CA）のクラスが得られます。この場合、グローバルマップF : K ⁿ → K ⁿは次のように与えられます。

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

このクラスは、古典的または標準的なセルラーオートマトンが通常、規則的なグラフまたはグリッド上で定義および研究され、頂点関数が通常同一であると想定されるため、一般化セルラーオートマトンと呼ばれます。

例: Y を頂点 {1,2,3,4} と辺 {1,2}、{2,3}、{3,4}、{1,4} を持つ円グラフ (Circ ₄と表記) とします。各頂点の状態空間をK = {0,1} とし、すべての頂点関数に対して2を法とする算術でnor ₃ ( x,y,z ) = (1 +  x )(1 +  y )(1 +  z ) で定義される関数 nor ₃  : K ³ → K を使用します。次に、たとえばシステム状態 (0,1,0,0) は、同期更新を使用して (0, 0, 0, 1) にマッピングされます。すべての遷移は、以下の位相空間に表示されます。

頂点関数が、ワードw = ( w ₁ , w ₂ , ... , w _m )またはv [ Y ]の順列= ( , )で指定されたシーケンスで非同期的に適用されると、シーケンシャル動的システム（SDS）のクラスが得られます。^[2]この場合、頂点関数から構築された Y局所マップFi_を導入すると便利です。${\displaystyle \pi}$${\displaystyle \pi_{1}}$${\displaystyle \pi _{2},\dots ,\pi _{n}}$

${\displaystyle 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 ^nは関数合成である。

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

更新シーケンスが順列である場合、この点を強調するために順列 SDSと呼ばれることがよくあります。

例: Y を頂点 {1,2,3,4} と辺 {1,2}、{2,3}、{3,4}、{1,4} を持つ円グラフ (Circ ₄と表記) とします。各頂点の状態空間をK ={0,1} とし、すべての頂点関数に対して2を法とする算術でnor ₃ ( x, y, z ) = (1 +  x )(1 +  y )(1 +  z ) で定義される関数 nor ₃  : K ³ → K を使用します。更新シーケンス (1,2,3,4) を使用すると、システム状態 (0, 1, 0, 0) は (0, 0, 1, 0) にマッピングされます。この順次動的システムのすべてのシステム状態遷移は、以下の位相空間に示されています。

たとえば、アプリケーションの観点から、GDS の 1 つ以上のコンポーネントに確率的要素が含まれているケースを検討するのは興味深いことです。動機となるアプリケーションには、完全には理解されていないプロセス (細胞内のダイナミクスなど) や、すべての実用的な目的において特定の側面が何らかの確率分布に従って動作すると思われるプロセスが含まれる可能性があります。また、決定論的原理によって制御されるアプリケーションもあり、その説明は非常に複雑または扱いにくいため、確率的近似を検討することが理にかなっています。

グラフ動的システムのすべての要素は、いくつかの方法で確率的にすることができます。たとえば、シーケンシャル動的システムでは、更新シーケンスを確率的にすることができます。各反復ステップで、対応する確率を持つ更新シーケンスの指定された分布から、更新シーケンスw をランダムに選択できます。更新シーケンスの一致する確率空間は、SDS マップの確率空間を誘導します。この点で研究する自然な対象は、この SDS マップのコレクションによって誘導される状態空間上のマルコフ連鎖です。このケースは更新シーケンス確率 GDSと呼ばれ、たとえば、特定の速度に従ってランダムに「イベント」が発生するプロセス (化学反応など)、並列計算/離散イベント シミュレーションでの同期、および後で説明する計算パラダイムによって動機付けられます。

確率的更新シーケンスのこの特定の例は、このようなシステムに関する 2 つの一般的な事実を示しています。確率的グラフ動的システムに移行すると、一般的に (1) マルコフ連鎖の研究 (GDS の構成要素によって制御される特定の構造を持つ) に行き着き、(2) 結果として得られるマルコフ連鎖は指数関数的な数の状態を持つ大きなものになる傾向があります。確率的 GDS の研究における中心的な目標は、縮小モデルを導出できるようにすることです。

頂点関数が確率的である場合、つまり関数確率 GDSの場合も考えられます。たとえば、ランダムブール ネットワークは、同期更新スキームを使用し、状態空間がK = {0, 1} である関数確率 GDS の例です。有限確率セル オートマトン(PCA) は、関数確率 GDS の別の例です。原理的には、相互作用粒子システム (IPS) のクラスは有限および無限PCAをカバーしますが、実際には、IPS に関する研究は主に無限の場合を対象としています。これは、無限の場合の方が、状態空間にさらに興味深いトポロジを導入できるためです。

グラフ動的システムは、生物学的ネットワークやソーシャル ネットワーク上の伝染病などの分散システムを捉えるための自然なフレームワークを構成し、その多くは複雑システムと呼ばれることがよくあります。

• 化学反応ネットワーク理論
• 動的ネットワーク分析（社会科学のトピック）
• 有限状態機械
• ホップフィールドネットワーク
• カウフマンネットワーク
• ペトリネット

• マコーリー、マシュー; モルトベイト、ヘニング S. (2009). 「グラフ動的システムのサイクル等価性」.非線形性. 22 (2): 421–436. arXiv : 0802.4412 . Bibcode :2009Nonli..22..421M. doi :10.1088/0951-7715/22/2/010. S2CID  17978550.
• ゴルビツキー、マーティン、スチュワート、イアン（2003）。『対称性の視点』バーゼル：ビルクハウザー。ISBN 0-8176-2171-7。

• グラフ動的システム - 相互作用ベースのシステム、その分析とシミュレーションのための数学的フレームワーク、Henning Mortveit 著