最大エントロピーランダムグラフモデル

最大エントロピーランダムグラフモデルは、一連の構造的制約（^{[ 1 ]}グローバル、分布、またはローカル） の下で最大エントロピーの原理に従う複雑なネットワークを研究するために使用されるランダムグラフモデルです。

概要

任意のランダムグラフモデル（固定のパラメータ値セットにおいて）はグラフ上に確率分布を生じ、考慮される分布クラス内で最大エントロピーとなるものは、ネットワーク推論^{[ 2 ]}（例：生物学的ネットワーク推論）に対する最大限不偏なヌルモデルであるという特別な特性を持つ。各モデルは、サイズ のグラフのセット（それぞれ、ある有限 に対して）上の確率分布の族を定義し、各グラフに対して定義された観測可能な値の制約のコレクション（固定の期待平均次数、特定形式の次数分布、特定の次数シーケンスなど）によってパラメータ化し、ラグランジュ乗数法によるエントロピー最大化とともにグラフ分布内で強制する。この文脈において「最大エントロピー」は単一のグラフのエントロピーではなく、ランダムグラフの確率的アンサンブル全体のエントロピーを指すことに留意する。 ${\displaystyle n}$ ${\displaystyle n>n_{0}}$ ${\displaystyle n_{0}}$ ${\displaystyle J}$ ${\displaystyle \{Q_{j}(G)\}_{j=1}^{J}}$ ${\displaystyle G}$

一般的に研究されているランダムネットワークモデルの中には、実は最大エントロピーのモデルがいくつかあり、例えばERグラフや(それぞれエッジの数に対して 1 つのグローバル制約を持つ)、構成モデル(CM) などがあります。^{[ 3 ]}およびソフト構成モデル(SCM) (それぞれノードごとの次数値に対して 1 つのローカル制約を持つ)。上記の 2 組のモデルにおいて重要な区別^{[ 4 ] [ 5 ]}は、制約がシャープ (つまり、アンサンブル内でサイズ グラフのセットのすべての要素が非ゼロの確率で満たす) か、ソフト (つまり、アンサンブル全体の平均で満たす) かという点です。前者 (シャープ) の場合はミクロカノニカル アンサンブル^{[ 6 ]}に対応し、最大エントロピーの条件により、すべてのグラフが等確率でを満たすことになります。後者 (ソフト) の場合はカノニカル^{[ 7 ]}で、指数ランダムグラフモデル(ERGM)が生成されます。 ${\displaystyle G(n,m)}$ ${\displaystyle G(n,p)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle Q_{j}(G)=q_{j}\forall j}$

モデル	制約タイプ	制約変数	確率分布
ER、${\displaystyle G(n,m)}$	シャープ、グローバル	合計エッジ数${\displaystyle |E(G)|}$	${\displaystyle 1/{\binom {\binom {n}{2}}{m}};\ m=|E(G)|}$
ER、${\displaystyle G(n,p)}$	ソフト、グローバル	予想される合計エッジ数${\displaystyle |E(G)|}$	${\displaystyle p^{|E(G)|}(1-p)^{{\binom {n}{2}}-|E(G)|}}$
構成モデル	シャープでローカル	各頂点の次数、${\displaystyle \{{\hat {k}}_{j}\}_{j=1}^{n}}$	${\displaystyle 1/\left\vert \Omega (\{{\hat {k}}_{j}\}_{j=1}^{n})\right\vert ;\Omega (\{k_{j}\}_{j=1}^{n})=\{g\in {\mathcal {G}}_{n}:k_{j}(g)={\hat {k}}_{j}\forall j\}\subset {\mathcal {G}}_{n}}$
ソフト構成モデル	ソフトでローカル	各頂点の期待次数、${\displaystyle \{{\hat {k}}_{j}\}_{j=1}^{n}}$	${\displaystyle Z^{-1}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right];\ -{\frac {\partial \ln Z}{\partial \psi _{j}}}={\hat {k}}_{j}}$

グラフの標準アンサンブル（一般的な枠組み）

頂点を持つ単純グラフの集合上の確率分布からなるランダムグラフモデルを構築すると仮定する。 このアンサンブルのギブスエントロピーは次のように与えられる。 ${\displaystyle \mathbb {P} (G)}$ ${\displaystyle {\mathcal {G}}_{n}}$ ${\displaystyle n}$ ${\displaystyle S[G]}$

${\displaystyle S[G]=-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)\log \mathbb {P} (G).}$

観測可能な値のアンサンブル平均値（平均次数、平均クラスタリング、平均最短経路長など）を調整可能にしたいので、グラフ分布に「ソフト」制約を 課します。${\displaystyle \{\langle Q_{j}\rangle \}_{j=1}^{J}}$ ${\displaystyle \{Q_{j}(G)\}_{j=1}^{J}}$ ${\displaystyle J}$

${\displaystyle \langle Q_{j}\rangle =\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)Q_{j}(G)=q_{j},}$

ここで、制約条件をラベル付けする。ラグランジュ乗数法を適用して、と正規化条件を満たしながらを最大化する分布を決定すると、次のようになる。^{[ 1 ]}${\displaystyle j=1,...,J}$ ${\displaystyle \mathbb {P} (G)}$ ${\displaystyle S[G]}$ ${\displaystyle \langle Q_{j}\rangle =q_{j}}$ ${\displaystyle \sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)=1}$

${\displaystyle \mathbb {P} (G)={\frac {1}{Z}}\exp \left[-\sum _{j=1}^{J}\psi _{j}Q_{j}(G)\right],}$

ここで、 は正規化定数（パーティション関数）であり、 は対応するインデックス付きグラフ観測可能量に結合されたパラメータ（ラグランジュ乗数）であり、平均してそれらのプロパティの望ましい値を持つグラフサンプルを生成するように調整できます。結果は指数族と標準アンサンブルであり、具体的にはERGM を生成します。 ${\displaystyle Z}$ ${\displaystyle \{\psi _{j}\}_{j=1}^{J}}$

エルデシュ・レーニモデル${\displaystyle G(n,m)}$

上記の標準的な枠組みでは、アンサンブル平均量 に制約が課されていました。これらの特性は平均的には を適切に設定することで指定可能な値を取りますが、個々の特定のインスタンスでは となる可能性があり、これは望ましくない場合があります。代わりに、より厳しい条件を課すことができます。つまり、非ゼロ確率を持つすべてのグラフは を正確に満たさなければなりません。これらの「厳しい」制約の下で、最大エントロピー分布が決定されます。これをエルデシュ・レーニイモデル で例示します。 ${\displaystyle \langle Q_{j}\rangle }$ ${\displaystyle \{\psi _{j}\}_{j=1}^{J}}$ ${\displaystyle G}$ ${\displaystyle Q_{j}(G)\neq q_{j}}$ ${\displaystyle Q_{j}(G)=q_{j}}$ ${\displaystyle G(n,m)}$

における明確な制約は、辺の数が固定されているという制約であり、^{[ 8 ]}つまり、 （確率 でインスタンス化される）アンサンブルから抽出されたすべてのグラフに対して となる。これにより、サンプル空間は（頂点上のすべてのグラフ）から部分集合 に制限される。これは、古典統計力学におけるミクロカノニカルアンサンブルと直接類似しており、ミクロカノニカルアンサンブルでは、システムは特定のエネルギー値のすべての状態の位相空間における薄い多様体に制限される。 ${\displaystyle G(n,m)}$ ${\displaystyle m}$ ${\displaystyle |\operatorname {E} (G)|=m}$ ${\displaystyle G}$ ${\displaystyle \mathbb {P} _{n,m}(G)}$ ${\displaystyle {\mathcal {G}}_{n}}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {G}}_{n,m}=\{g\in {\mathcal {G}}_{n};|\operatorname {E} (g)|=m\}\subset {\mathcal {G}}_{n}}$

標本空間を に制限すると、正規化以外に満たすべき外部制約はなくなるため、ラグランジュ乗数を用いずにを最大化することを選択します。外部制約がない場合のエントロピー最大化分布は、標本空間上の一様分布であることがよく知られています（最大エントロピー確率分布 を参照）。そこから、以下の式が得られます。 ${\displaystyle {\mathcal {G}}_{n,m}}$ ${\displaystyle \mathbb {P} _{n,m}(G)}$ ${\displaystyle S[G]}$

${\displaystyle \mathbb {P} _{n,m}(G)={\frac {1}{|{\mathcal {G}}_{n,m}|}}={\binom {\binom {n}{2}}{m}}^{-1},}$

ここで、二項係数に関する最後の式は、可能なエッジの間にエッジを配置する方法の数であり、したがっての濃度です。 ${\displaystyle m}$ ${\displaystyle {\binom {n}{2}}}$ ${\displaystyle {\mathcal {G}}_{n,m}}$

一般化

単純グラフの一般化については、様々な最大エントロピーアンサンブルが研究されてきた。これらには、例えば、単体複体のアンサンブル^{[ 9 ]}や、与えられた期待次数列を持つ重み付きランダムグラフ ^{[ 10 ]などが含まれる。}

参照

• 最大エントロピーの原理
• 最大エントロピー確率分布
• ラグランジュ乗数法
• ヌルモデル
• ランダムグラフ
• 指数ランダムグラフモデル
• 標準的なアンサンブル
• ミクロカノニカルアンサンブル

参考文献

1. Park, Juyong; MEJ Newman (2004-05-25). 「ネットワークの統計力学」. arXiv : cond-mat/0405566 .
2. van der Hoorn, Pim; Gabor Lippner; Dmitri Krioukov (2017-10-10). 「与えられたべき乗法則次数分布を持つ疎最大エントロピーランダムグラフ」arXiv : 1705.10261 .
3. ニューマン、マーク (2010).ネットワーク：入門 - オックスフォード・スカラーシップ. doi : 10.1093/acprof:oso/9780199206650.001.0001 . ISBN 978-0-19-920665-0. 2023年2月4日時点のオリジナルよりアーカイブ。2018年9月13日閲覧。
4. Garlaschelli, Diego; den Hollander, Frank; Roccaverde, Andrea (2018-07-13). 「ランダムグラフにおけるアンサンブル同値性の破れの背後にある共分散構造」. Journal of Statistical Physics . 173 ( 3–4 ): 644– 662. arXiv : 1711.04273 . Bibcode : 2018JSP...173..644G . doi : 10.1007/s10955-018-2114-x . ISSN 0022-4715 . 
5. Roccaverde, Andrea (2018年8月). 「アンサンブル同値性の破れは制約の数において単調か？」Indagationes Mathematicae . 30 : 7–25 . arXiv : 1807.02791 . doi : 10.1016/j.indag.2018.08.001 . ISSN 0019-3577 . 
6. Bianconi, G. (2018-08-21).多層ネットワーク：構造と機能. オックスフォード大学出版局. ISBN 978-0-19-875391-9. 2023年2月4日時点のオリジナルよりアーカイブ。2018年9月13日閲覧。
7. Anand, K.; Bianconi, G. (2009). 「ネットワークのエントロピー測定：複雑トポロジーの情報理論に向けて」. Physical Review E. 80 ( 4) 045102. arXiv : 0907.1514 . Bibcode : 2009PhRvE..80d5102A . doi : 10.1103/PhysRevE.80.045102 . PMID 19905379 . 
8. エルデシュ、P.;レニー、A. (2022)。「ランダムグラフについて。I」(PDF)。出版物 Mathematicae Debrecen。6 ( 3–4 ): 290–297。土井: 10.5486/PMD.1959.6.3-4.12。2020-08-07 にオリジナルからアーカイブ(PDF)されました。2018年9月13日に取得。
9. ズエフ、コンスタンチン;あるいはアイゼンバーグ。ドミトリ・クリウコフ (2015-10-29)。 「指数関数的ランダム単純複素数」。arXiv : 1502.05032。
10. Hillar, Christopher; Andre Wibisono (2013-08-26). 「グラフ上の最大エントロピー分布」arXiv : 1301.3321 .