Random graph model in applied mathematics
応用数学において、 ソフト構成モデル（SCM） は、サンプリングされた グラフの 次数列 の 期待値 に制約がある状態で 最大エントロピーの原理 に従う ランダムグラフ モデルである 。 [1] 構成モデル （CM）が特定の次数列のランダムグラフを均一にサンプリングするのに対し 、SCMはすべてのネットワーク実現にわたって平均して指定された次数列を保持するだけである。この意味で、SCMはCMに比べて非常に緩い制約（「厳しい」制約ではなく「ソフトな」制約 [2] ）を持つ。サイズのグラフのSCMは、 サイズ の任意のグラフをサンプリングする確率がゼロではない が、CMは正確に規定された接続構造を持つグラフだけに制限される。 n {\displaystyle n} n {\displaystyle n}
SCM は、というラベルの付いた 頂点 ( ) を 持つ ランダムグラフの 統計的アンサンブル で、 (サイズ のグラフの集合) に 確率分布を 生成します。アンサンブルには 制約が課せられており、 すべての について、 頂点の 次数 の アンサンブル平均 は指定された値 に等しくなります 。モデルは、 そのサイズ と期待される次数シーケンスによって完全に パラメーター化されます 。これらの制約は、ローカル (各頂点に 1 つの制約が関連付けられている) かつソフト (特定の観測可能な量のアンサンブル平均に対する制約) であるため、制約の数が多い標準的なアンサンブルが生成されます 。 [ 2 ] 条件 は、 ラグランジュ乗数法 によってアンサンブルに課せられます ( 最大エントロピーランダムグラフモデル を 参照)。 G {\displaystyle G} n {\displaystyle n} n = | V ( G ) | {\displaystyle n=|V(G)|} { v j } j = 1 n = V ( G ) {\displaystyle \{v_{j}\}_{j=1}^{n}=V(G)} G n {\displaystyle {\mathcal {G}}_{n}} n {\displaystyle n} n {\displaystyle n} k j {\displaystyle k_{j}} v j {\displaystyle v_{j}} k ^ j {\displaystyle {\widehat {k}}_{j}} v j ∈ V ( G ) {\displaystyle v_{j}\in V(G)} n {\displaystyle n} { k ^ j } j = 1 n {\displaystyle \{{\widehat {k}}_{j}\}_{j=1}^{n}} ⟨ k j ⟩ = k ^ j {\displaystyle \langle k_{j}\rangle ={\widehat {k}}_{j}}
確率分布の導出 SCMがグラフを生成する 確率は、 制約 と正規化の下で ギブスエントロピーを 最大化することによって決定されます 。これは、以下の 多重制約 ラグランジュ関数を 最適化する ことに相当します。 P SCM ( G ) {\displaystyle \mathbb {P} _{\text{SCM}}(G)} G {\displaystyle G} S [ G ] {\displaystyle S[G]} ⟨ k j ⟩ = k ^ j , j = 1 , … , n {\displaystyle \langle k_{j}\rangle ={\widehat {k}}_{j},\ j=1,\ldots ,n} ∑ G ∈ G n P SCM ( G ) = 1 {\displaystyle \sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)=1}
L ( α , { ψ j } j = 1 n ) = − ∑ G ∈ G n P SCM ( G ) log P SCM ( G ) + α ( 1 − ∑ G ∈ G n P SCM ( G ) ) + ∑ j = 1 n ψ j ( k ^ j − ∑ G ∈ G n P SCM ( G ) k j ( G ) ) , {\displaystyle {\begin{aligned}&{\mathcal {L}}\left(\alpha ,\{\psi _{j}\}_{j=1}^{n}\right)\\[6pt]={}&-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)\log \mathbb {P} _{\text{SCM}}(G)+\alpha \left(1-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)\right)+\sum _{j=1}^{n}\psi _{j}\left({\widehat {k}}_{j}-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)k_{j}(G)\right),\end{aligned}}} ここで 、およびは制約条件（正規化と期待次数列） によって固定される乗数で ある。 任意 の について上記の微分をゼロにすると 、 α {\displaystyle \alpha } { ψ j } j = 1 n {\displaystyle \{\psi _{j}\}_{j=1}^{n}} n + 1 {\displaystyle n+1} n + 1 {\displaystyle n+1} P SCM ( G ) {\displaystyle \mathbb {P} _{\text{SCM}}(G)} G ∈ G n {\displaystyle G\in {\mathcal {G}}_{n}}
0 = ∂ L ( α , { ψ j } j = 1 n ) ∂ P SCM ( G ) = − log P SCM ( G ) − 1 − α − ∑ j = 1 n ψ j k j ( G ) ⇒ P SCM ( G ) = 1 Z exp [ − ∑ j = 1 n ψ j k j ( G ) ] , {\displaystyle 0={\frac {\partial {\mathcal {L}}\left(\alpha ,\{\psi _{j}\}_{j=1}^{n}\right)}{\partial \mathbb {P} _{\text{SCM}}(G)}}=-\log \mathbb {P} _{\text{SCM}}(G)-1-\alpha -\sum _{j=1}^{n}\psi _{j}k_{j}(G)\ \Rightarrow \ \mathbb {P} _{\text{SCM}}(G)={\frac {1}{Z}}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right],} 定数 [3] は分布を正規化する 分配関数 である。上記の指数式はすべての に適用され 、したがって は確率分布となる。したがって、 によってパラメータ化された 指数族 が得られ、これは期待次数列 と以下の同値な式で関連付けられる。 Z := e α + 1 = ∑ G ∈ G n exp [ − ∑ j = 1 n ψ j k j ( G ) ] = ∏ 1 ≤ i < j ≤ n ( 1 + e − ( ψ i + ψ j ) ) {\displaystyle Z:=e^{\alpha +1}=\sum _{G\in {\mathcal {G}}_{n}}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right]=\prod _{1\leq i<j\leq n}\left(1+e^{-(\psi _{i}+\psi _{j})}\right)} G ∈ G n {\displaystyle G\in {\mathcal {G}}_{n}} { ψ j } j = 1 n {\displaystyle \{\psi _{j}\}_{j=1}^{n}} { k ^ j } j = 1 n {\displaystyle \{{\widehat {k}}_{j}\}_{j=1}^{n}}
⟨ k q ⟩ = ∑ G ∈ G n k q ( G ) P SCM ( G ) = − ∂ log Z ∂ ψ q = ∑ j ≠ q 1 e ψ q + ψ j + 1 = k ^ q , q = 1 , … , n . {\displaystyle \langle k_{q}\rangle =\sum _{G\in {\mathcal {G}}_{n}}k_{q}(G)\mathbb {P} _{\text{SCM}}(G)=-{\frac {\partial \log Z}{\partial \psi _{q}}}=\sum _{j\neq q}{\frac {1}{e^{\psi _{q}+\psi _{j}}+1}}={\widehat {k}}_{q},\ q=1,\ldots ,n.}
参考文献 ^ van der Hoorn, Pim; Gabor Lippner; Dmitri Krioukov (2017-10-10). 「与えられたべき乗法則次数分布を持つ疎最大エントロピーランダムグラフ」 arXiv : 1705.10261 . ^ ab Garlaschelli, Diego; Frank den Hollander; Andrea Roccaverde (2018年1月30日). 「ランダムグラフにおけるアンサンブル同値性の破れの背後にある共存構造」 (PDF) . 2023年2月4日時点のオリジナルより アーカイブ (PDF) . 2018年 9月14日 閲覧 。 ^ Park, Juyong; MEJ Newman (2004-05-25). 「ネットワークの統計力学」. arXiv : cond-mat/0405566 . 
![{\displaystyle S[G]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d93ef8dea8ea1040e026651af20df12e03f72261)
![{\displaystyle {\begin{aligned}&{\mathcal {L}}\left(\alpha ,\{\psi _{j}\}}_{j=1}^{n}\right)\\[6pt]={}&-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)\log \mathbb {P} _{\text{SCM}}(G)+\alpha \left(1-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)\right)+\sum _{j=1}^{n}\psi _{j}\left({\widehat {k}}_{j}-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)k_{j}(G)\right),\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/426a3cc31489b0b0465255e44a37e34e91a0330f)
![{\displaystyle 0={\frac {\partial {\mathcal {L}}\left(\alpha ,\{\psi _{j}\}}_{j=1}^{n}\right)}{\partial \mathbb {P} _{\text{SCM}}(G)}}=-\log \mathbb {P} _{\text{SCM}}(G)-1-\alpha -\sum _{j=1}^{n}\psi _{j}k_{j}(G)\ \Rightarrow \ \mathbb {P} _{\text{SCM}}(G)={\frac {1}{Z}}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54cf3d859575acc9547b31a499f5c0e6a8fd5bb7)
![{\displaystyle Z:=e^{\alpha +1}=\sum _{G\in {\mathcal {G}}_{n}}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right]=\prod _{1\leq i<j\leq n}\left(1+e^{-(\psi _{i}+\psi _{j})}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55d4faa8b4a693d83f99ba0e24aa0ca48517c9ee)
