グラフオン

グラフオンによって定義された交換可能なランダムグラフの実現。グラフオンはマゼンタのヒートマップ（右下）として示されています。サイズのランダムグラフは、各頂点に潜在確率変数 （縦軸の値）を独立に割り当て、各辺を確率で独立に含めることで生成されます。例えば、辺（緑の点線）は確率で存在します 。右側の四角形の緑のボックスは、との値を表しています。左上のパネルは、グラフの実現を隣接行列として示しています${\displaystyle n}$ ${\displaystyle k\in \{1,\dotsc,n\}}$ ${\displaystyle U_{k}\sim \mathrm {U} (0,1)}$ ${\displaystyle (k,\ell)}$ ${\displaystyle f(U_{k},U_{\ell})}$ ${\displaystyle (3,5)}$ ${\displaystyle f(0.72,0.9)}$ ${\displaystyle (u_{3},u_{5})}$ ${\displaystyle (u_{5},u_{3})}$

グラフ理論と統計学において、グラフオン（グラフ極限とも呼ばれる）は対称的な 測定可能な関数であり、稠密グラフの研究で重要である。グラフオンは、稠密グラフの列の極限の自然な概念として、また、交換可能なランダムグラフモデルの基本的な定義対象として出現する。グラフオンは、次の2つの観察結果によって稠密グラフと結びついている。グラフオンによって定義されるランダムグラフモデルは、ほぼ確実に稠密グラフを生じ、正則性補題によって、グラフオンは任意の大きな稠密グラフの構造を捉える。 ${\displaystyle W:[0,1]^{2}\to [0,1]}$

統計的定式化

グラフオンは対称的な測定可能な関数です。通常、グラフオンは次のスキームに従って交換可能なランダムグラフモデルを定義するものと理解されています ${\displaystyle W:[0,1]^{2}\to [0,1]}$

1. グラフの各頂点には独立したランダムな値が割り当てられる${\displaystyle j}$ ${\displaystyle u_{j}\sim U[0,1]}$
2. エッジは確率 でグラフに独立して含まれます。${\displaystyle (i,j)}$ ${\displaystyle W(u_{i},u_{j})}$

ランダムグラフモデルが交換可能ランダムグラフモデルであるためには、（ランダムな可能性のある）グラフオンを用いてこのように定義できる必要がある。固定グラフオンに基づくモデルは、ランダムグラフのエルデシュ・レーニイモデルとの類推から、 と表記されることもある。このようにグラフオンから生成されたグラフは、 -ランダムグラフと呼ばれる。 ${\displaystyle W}$ ${\displaystyle \mathbb {G} (n,W)}$ ${\displaystyle W}$ ${\displaystyle W}$

この定義と大数の法則から、交換可能なランダムグラフモデルはほぼ確実に稠密であることがわかります。^[1]${\displaystyle W\neq 0}$

例

グラフオンの最も単純な例は、ある定数の場合です。この場合、関連する交換可能ランダムグラフモデルは、各 辺を独立に確率で含むエルデシュ・レーニモデルです${\displaystyle W(x,y)\equiv p}$ ${\displaystyle p\in [0,1]}$ ${\displaystyle G(n,p)}$ ${\displaystyle p}$

代わりに、次のように区分的に定数であるグラフオンから始めるとします。

1. 単位正方形をブロックに分割し、${\displaystyle k\times k}$
2. ブロックに等しい設定、${\displaystyle W}$ ${\displaystyle p_{lm}}$ ${\displaystyle (\ell ,m)^{\text{th}}}$

結果として得られる交換可能なランダムグラフモデルは、エルデシュ・レーニイモデルの一般化である コミュニティ確率ブロックモデルである。これは、それぞれパラメータを持つ異なるエルデシュ・レーニイグラフと、それらの間にバイグラフを持つランダムグラフモデルとして解釈できる。ここで、ブロックとブロック間の可能な辺はそれぞれ独立に確率 で含まれる。 ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle p_{\ell \ell }}$ ${\displaystyle (\ell ,\ell )}$ ${\displaystyle (m,m)}$ ${\displaystyle p_{\ell m}}$

他の多くの一般的なランダムグラフモデルは、何らかのグラフオンによって定義された交換可能なランダムグラフモデルとして理解することができ、詳細な調査はOrbanzとRoyに含まれています。^[1]

共同交換可能な隣接行列

サイズのランダムグラフは、ランダム隣接行列として表すことができます。異なるサイズのランダムグラフ間に（射影性の意味で）一貫性を持たせるためには、ランダム変数の無限配列の左上部分行列として生じる隣接行列の列を調べるのが自然です。これにより、 にノードを追加し、 のエッジをサンプリングすることでを生成できます。この観点から、ランダムグラフはランダムな無限対称配列 として定義されます。 ${\displaystyle n}$ ${\displaystyle n\times n}$ ${\displaystyle n\times n}$ ${\displaystyle G_{n}}$ ${\displaystyle G_{n-1}}$ ${\displaystyle (j,n)}$ ${\displaystyle j<n}$ ${\displaystyle (X_{ij})}$

古典的確率における交換可能な列の根本的な重要性に従えば、ランダムグラフの設定において類似の概念を探すのは自然なことです。そのような概念の一つは、共存交換可能な行列、すなわち以下の条件を満たすランダム行列によって与えられます。

${\displaystyle (X_{ij})\ {\overset {d}{=}}\,(X_{\sigma (i)\sigma (j)})}$

自然数のすべての順列に対して、分布が等しいことを意味します。直感的に言えば、この条件は、ランダムグラフの分布が頂点のラベル付けによって変化しないことを意味します。つまり、頂点のラベルには情報が含まれていないということです。 ${\displaystyle \sigma }$ ${\displaystyle {\overset {d}{=}}}$

交換可能なランダム隣接行列に対する表現定理は、交換可能な列に対するデ・フィネッティの表現定理に類似している。これは、交換可能な配列に対するオルダス＝フーバー定理の特殊なケースであり、この設定において、ランダム行列は以下のように生成されることを主張する。 ${\displaystyle (X_{ij})}$

1. 個別にサンプル採取${\displaystyle u_{j}\sim U[0,1]}$
2. ${\displaystyle X_{ij}=X_{ji}=1}$ 確率的に独立してランダムに${\displaystyle W(u_{i},u_{j}),}$

ここでは（ランダムな可能性のある）グラフオンです。つまり、ランダムグラフモデルが共有交換可能な隣接行列を持つのは、それが何らかのグラフオンによって定義された共有交換可能なランダムグラフモデルである場合のみです。 ${\displaystyle W:[0,1]^{2}\to [0,1]}$

グラフ推定

識別可能性の問題により、グラフオン関数とノードの潜在位置のどちらも推定することは不可能であり、グラフオン推定には主に2つの方向性がある。1つは同値類までの推定を目的とするものであり、^{[2] [3]}、もう1つは、によって誘導される確率行列を推定するものである。^{[4] [5]}${\displaystyle W}$ ${\displaystyle u_{i},}$ ${\displaystyle W}$ ${\displaystyle W}$

解析的定式化

任意の頂点グラフは、その隣接行列と同一視できます。この行列はステップ関数に対応し、 各 に対して がの 要素に等しくなる ように区間に 分割することによって定義されます。この関数は、 グラフ の関連グラフオンです${\displaystyle n}$ ${\displaystyle \{1,2,\dots ,n\}}$ ${\displaystyle A_{G}}$ ${\displaystyle W_{G}:[0,1]^{2}\to [0,1]}$ ${\displaystyle [0,1]}$ ${\displaystyle I_{1},I_{2},\dots ,I_{n}}$ ${\displaystyle I_{j}}$ $${\displaystyle \left({\frac {j-1}{n}},{\frac {j}{n}}\right)}$$ ${\displaystyle (x,y)\in I_{i}\times I_{j}}$ ${\displaystyle W_{G}(x,y)}$ ${\displaystyle (i,j)^{\text{th}}}$ ${\displaystyle A_{G}}$ ${\displaystyle W_{G}}$ ${\displaystyle G}$

一般に、の頂点数が無限大となるグラフ列がある場合、関数 の極限挙動を考慮することで、その列の極限挙動を分析できます。これらのグラフが収束する場合（収束の適切な定義に従って）、これらのグラフの極限は、関連する関数の極限に対応すると予想されます。 ${\displaystyle (G_{n})}$ ${\displaystyle G_{n}}$ ${\displaystyle (W_{G_{n}})}$

このことが、グラフの列の極限の概念を捉える対称可測関数としてグラフオン（「グラフ関数」の略）を定義する動機となっている。稠密グラフの列に対しては、一見異なる収束の概念が複数存在し、それら全てにおいて自然な極限対象はグラフオンであることが分かっている。^[6]${\displaystyle W:[0,1]^{2}\to [0,1]}$

例

定数グラフオン

ある固定パラメータを持つエルデシュ・レーニイランダムグラフの列を取ります。直感的に、が無限大に近づくにつれて、このグラフ列の極限はこれらのグラフの辺密度によってのみ決まります。グラフオン空間では、このような列はほぼ確実に定数に収束することがわかり、これは上記の直感を捉えています ${\displaystyle (G_{n})}$ ${\displaystyle G_{n}=G(n,p)}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle W(x,y)\equiv p}$

半グラフ

を頂点と 上の二部グラフとし、が のときちょうどに隣接するものとすることで定義される半グラフの列 をとる。頂点が提示された順序で並べられている場合、隣接行列は「半正方形」ブロック行列の2つの頂点が1で埋められ、残りの要素は0になる。例えば、 の隣接行列は次のように与えられる ${\displaystyle (H_{n})}$ ${\displaystyle H_{n}}$ ${\displaystyle 2n}$ ${\displaystyle u_{1},u_{2},\dots ,u_{n}}$ ${\displaystyle v_{1},v_{2},\dots ,v_{n}}$ ${\displaystyle u_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle i\leq j}$ ${\displaystyle A_{H_{n}}}$ ${\displaystyle H_{3}}$

$${\displaystyle {\begin{bmatrix}0&0&0&1&1&1\\0&0&0&0&1&1\\0&0&0&0&0&1\\1&0&0&0&0&0\\1&1&0&0&0&0\\1&1&1&0&0&0\end{bmatrix}}.}$$

が大きくなるにつれて、これらの1の角は「滑らか」になります。この直感に一致して、数列は のときは、それ以外のときは で定義される半グラフオンに収束します。 ${\displaystyle n}$ ${\displaystyle (H_{n})}$ ${\displaystyle W}$ ${\displaystyle W(x,y)=1}$ ${\displaystyle |x-y|\geq 1/2}$ ${\displaystyle W(x,y)=0}$

完全二部グラフ

等しい大きさの部分を持つ完全二部グラフの列を取ります。一方の部分のすべての頂点を先頭に、もう一方の部分の頂点を末尾に配置するように頂点を並べると、隣接行列は、1のブロックが2つ、0のブロックが2つあるブロック非対角行列のように見えます。例えば、隣接行列は次のように表されます ${\displaystyle (K_{n,n})}$ ${\displaystyle (K_{n,n})}$ ${\displaystyle K_{2,2}}$

$${\displaystyle {\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}.}$$

が大きくなるにつれて、隣接行列のこのブロック構造は一定のままとなり、このグラフのシーケンスは、およびの場合は常に、それ以外の場合は で定義される「完全な二部」グラフオンに収束し ます。 ${\displaystyle n}$ ${\displaystyle W}$ ${\displaystyle W(x,y)=1}$ ${\displaystyle \min(x,y)\leq 1/2}$ ${\displaystyle \max(x,y)>1/2}$ ${\displaystyle W(x,y)=0}$

の頂点を交互に並べると、隣接行列は0と1のチェス盤のような構造になります。例えば、この順序付けでは、の隣接行列は次のように表されます 。${\displaystyle K_{n,n}}$ ${\displaystyle K_{2,2}}$

$${\displaystyle {\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}.}$$

が大きくなるにつれて、隣接行列はますます細かいチェス盤状になります。このような挙動にもかかわらず、 の極限は一意であり、例3のグラフオンが得られるようにする必要があります。つまり、グラフの列の収束を正式に定義する場合、極限の定義は頂点のラベル付けに依存しない必要があります。 ${\displaystyle n}$ ${\displaystyle (K_{n,n})}$

Wランダムグラフの限界

固定されたグラフオン を描き、 W {\displaystyle W} -ランダムグラフのランダムな列を取ります。すると、このセクションの最初の例と同様に、 はほぼ確実に に収束することがわかります。 ${\displaystyle (G_{n})}$ ${\displaystyle G_{n}\sim \mathbb {G} (n,W)}$ ${\displaystyle W}$ ${\displaystyle (G_{n})}$ ${\displaystyle W}$

グラフオンからグラフパラメータを復元する

グラフとそれに関連するグラフオンが与えられている場合、の変換を積分することでのグラフ理論的特性とパラメータを復元できます。例えば、 の辺密度（つまり、平均次数を頂点数で割ったもの）は積分 で与えられます 。 これは、が値であり、 の各辺が に等しい 領域 に対応するためです。 ${\displaystyle G}$ ${\displaystyle W=W_{G}}$ ${\displaystyle G}$ ${\displaystyle W}$ ${\displaystyle G}$ $${\displaystyle \int _{0}^{1}\int _{0}^{1}W(x,y)\;\mathrm {d} x\,\mathrm {d} y.}$$ ${\displaystyle W}$ ${\displaystyle \{0,1\}}$ ${\displaystyle (i,j)}$ ${\displaystyle G}$ ${\displaystyle I_{i}\times I_{j}}$ ${\displaystyle 1/n^{2}}$ ${\displaystyle W}$ ${\displaystyle 1}$

同様の推論により、三角形の密度は ${\displaystyle G}$ $${\displaystyle {\frac {1}{6}}\int _{0}^{1}\int _{0}^{1}\int _{0}^{1}W(x,y)W(y,z)W(z,x)\;\mathrm {d} x\,\mathrm {d} y\,\mathrm {d} z.}$$

収束の概念

2つのグラフ間の距離を測定する方法は多岐にわたります。グラフの極値特性を「保存する」指標に関心がある場合、ランダムグラフを類似グラフとして識別する指標に着目すべきです。例えば、エルデシュ・レーニイモデルとは独立に、ある固定された に対して2つのグラフをランダムに描画した場合、「妥当な」指標の下では、これらの2つのグラフ間の距離は、 が大きい に対して高い確率でゼロに近づくはずです。 ${\displaystyle G(n,p)}$ ${\displaystyle p}$ ${\displaystyle n}$

単純に考えれば、同じ頂点集合上に2つのグラフがある場合、それらの距離を、一方のグラフから他方のグラフへ移動するために追加または削除する必要がある辺の数、つまり編集距離と定義できるでしょう。しかし、編集距離はランダムグラフを類似グラフとして識別するものではありません。実際、 から独立して描画された2つのグラフの期待される（正規化された）編集距離は です。 ${\displaystyle G(n,{\tfrac {1}{2}})}$ ${\displaystyle {\tfrac {1}{2}}}$

密なランダムグラフにおいて、私たちが求める意味で適切に動作する自然な指標が2つあります。1つ目はサンプリング指標で、2つのグラフのサブグラフの分布が近い場合、2つのグラフは近いとみなされます。2つ目はエッジ不一致指標で、2つのグラフのエッジ密度が対応するすべての頂点サブセットにおいて近い場合、2つのグラフは近いとみなされます。

驚くべきことに、グラフの列は、一方の計量に関して収束するときと、もう一方の計量に関して収束する。さらに、両方の計量における極限対象はグラフオンであることが判明した。これら2つの収束の概念の同値性は、準ランダムグラフの様々な概念が同値であることを反映している。^[7]

準同型密度

2つのグラフ と の間の距離を測る1つの方法は、それらの相対的な部分グラフ数を比較することです。つまり、各グラフについて、と におけるのコピー数を比較することができます。これらの数がすべてのグラフ について近い場合、直感的にと は似たようなグラフです。しかし、部分グラフを直接扱うよりも、グラフ準同型を扱う方が簡単であることがわかります。これは、大きく密なグラフを扱う場合には問題ありません。なぜなら、このシナリオでは、固定グラフの部分グラフの数とグラフ準同型の数は漸近的に等しくなるからです ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle H}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle H}$

2つのグラフ と が与えられたとき、における の準同型 密度は、 からへのグラフ準同型写像の数として定義されます。言い換えれば、の頂点から の頂点へのランダムに選択された写像が、 の隣接頂点を の隣接頂点に送る確率です。 ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle t(F,G)}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle t(F,G)}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$

グラフオンは準同型密度を計算する簡単な方法を提供します。実際、グラフオンと別のグラフが与えられたとき、 ${\displaystyle G}$ ${\displaystyle W_{G}}$ ${\displaystyle F}$

$${\displaystyle t(F,G)=\int \prod _{(i,j)\in E(F)}W_{G}(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

ここで、積分は多次元であり、単位超立方体 上でとられる。これは、上記の積分関数が に等しい場合を考えることによって、付随グラフンの定義から導かれる。そして、同じ積分を用いて と定義することで、 準同型密度の定義を任意のグラフン に拡張することができる。${\displaystyle [0,1]^{V(F)}}$ ${\displaystyle 1}$ ${\displaystyle W}$

$${\displaystyle t(F,W)=\int \prod _{(i,j)\in E(F)}W(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

任意のグラフに対して。 ${\displaystyle F}$

この設定において、グラフ列が左収束するとは、任意の固定グラフ に対して準同型密度列が収束することである。定義だけでは明らかではないが、 がこの意味で収束する場合、任意のグラフ に対して同時に となる グラフオンが常に存在する 。 ${\displaystyle (G_{n})}$ ${\displaystyle F}$ ${\displaystyle \left(t(F,G_{n})\right)}$ ${\displaystyle (G_{n})}$ ${\displaystyle W}$ ${\displaystyle F}$ $${\displaystyle \lim _{n\to \infty }t(F,G_{n})=t(F,W)}$$

切断距離

同じ頂点集合上の2つのグラフとを取ります。これらのグラフは同じ頂点を共有しているため、距離を測定する1つの方法は、頂点集合の部分集合に限定し、そのような部分集合の各ペアについて、からまでの辺の数と、との間の辺の数を比較することです。これらの数値がすべての部分集合のペアで（頂点の総数と比較して）似ている場合、と は類似したグラフである と考えられます${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle X,Y}$ ${\displaystyle e_{G}(X,Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle G}$ ${\displaystyle e_{H}(X,Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$

この距離の概念の予備的な定式化として、サイズ の同じ頂点集合上の任意のグラフのペアとに対して、との間のラベル付きカット距離を次のように 定義する。${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle V}$ ${\displaystyle |V|=n}$ ${\displaystyle G}$ ${\displaystyle H}$

$${\displaystyle d_{\square }(G,H)={\frac {1}{n^{2}}}\max _{X,Y\subseteq V}\left|e_{G}(X,Y)-e_{H}(X,Y)\right|.}$$

言い換えれば、ラベル付きカット距離は、と間の辺密度の最大差異を符号化する。この概念をグラフオンに一般化するには、辺密度を関連するグラフオンで表すと、次の式が得られる。 ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle {\tfrac {1}{n^{2}}}e_{G}(X,Y)}$ ${\displaystyle W_{G}}$

$${\displaystyle d_{\square }(G,H)=\max _{X,Y\subseteq V}\left|\int _{I_{X}}\int _{I_{Y}}W_{G}(x,y)-W_{H}(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$

ここで、はと の頂点に対応する区間の和集合である。この定義は、比較対象となる2つのグラフが共通の頂点集合を持たない場合でも適用できる点に注意されたい。このことから、より一般的な定義が導かれる。 ${\displaystyle I_{X},I_{Y}\subseteq [0,1]}$ ${\displaystyle X}$ ${\displaystyle Y}$

定義1.任意の対称測定可能な関数 に対して、 のカットノルムを次の量と 定義する。${\displaystyle f:[0,1]^{2}\to \mathbb {R} }$ ${\displaystyle f}$

$${\displaystyle \lVert f\rVert _{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S}\int _{T}f(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$ 単位間隔の 測定可能な部分集合すべてにわたって行われた。 ^[6]${\displaystyle S,T}$

これは、等式 が得られるため、以前のラベル付きカット距離の概念を捉えています。 ${\displaystyle \lVert W_{G}-W_{H}\rVert _{\square }=d_{\square }(G,H)}$

この距離尺度には依然として大きな制限が1つあります。それは、2つの同型グラフに非ゼロの距離を割り当てることができるということです。同型グラフの距離がゼロであることを保証するためには、頂点のあらゆる可能な「再ラベル付け」に対して最小のカットノルムを計算する必要があります。これが、カット距離の以下の定義の根拠となります。

定義2.任意のグラフオンとに対して、それらのカット距離を次のように 定義する。${\displaystyle U}$ ${\displaystyle W}$

$${\displaystyle \delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }}$$ ここでは写像 との合成であり、最小値は単位区間からそれ自身への測度保存の全単射にわたって取られる。 ^[8]${\displaystyle W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))}$ ${\displaystyle W}$ ${\displaystyle \varphi }$

2 つのグラフ間のカット距離は、それらの関連するグラフオン間のカット距離として定義されます。

グラフ列がカット距離 に関して収束するとは、それがカット距離 に関してコーシー列であることを意味する。定義から直接導かれるわけではないが、そのようなグラフ列がコーシー列である場合、それは必ず何らかのグラフオン に収束する。 ${\displaystyle (G_{n})}$ ${\displaystyle \delta _{\square }}$ ${\displaystyle W}$

収束の同値性

結局のところ、任意のグラフ列に対して、左収束はカット距離での収束と同値であり、さらに極限グラフオンも同じです。同じ定義を用いてグラフオン自体の収束を考えることもでき、同じ同値性が成り立ちます。実際、収束の両方の概念は、計数補題と呼ばれるものを通じてより強く関連しています。^[6]${\displaystyle (G_{n})}$ ${\displaystyle W}$

計数補題。任意のグラフオンとに対して、 ${\displaystyle U}$ ${\displaystyle W}$

$${\displaystyle |t(F,U)-t(F,W)|\leq e(F)\delta _{\square }(U,W)}$$ すべてのグラフに対して。 ${\displaystyle F}$

「計数補題」という名称は、グラフの部分グラフ数え上げに類似する準同型密度 に対してこの補題が与える境界に由来する。この補題は、正則性分割の分野に現れるグラフ計数補題の一般化であり、カット距離の下での収束は左収束を意味することを直ちに示す。 ${\displaystyle t(F,W)}$

逆数え上げ補題。任意の実数に対して、任意のグラフオンのペアとに対して 、${\displaystyle \varepsilon >0}$ ${\displaystyle \eta >0}$ ${\displaystyle k}$ ${\displaystyle U}$ ${\displaystyle W}$

$${\displaystyle |t(F,U)-t(F,W)|\leq \eta }$$ を満たす すべてのグラフに対して、 が成り立つ必要があります。 ${\displaystyle F}$ ${\displaystyle v(F)\leq k}$ ${\displaystyle \delta _{\square }(U,W)<\varepsilon }$

この補題は、左収束はカット距離での収束を意味することを示しています。

グラフオンの空間

すべてのグラフオンの集合をとり、のときはいつでも2つのグラフオンを同一視することにより、カット距離を計量にすることができます。結果として得られるグラフオンの空間は と表記され、 と共に計量空間を形成します。 ${\displaystyle U\sim W}$ ${\displaystyle \delta _{\square }(U,W)=0}$ ${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$ ${\displaystyle \delta _{\square }}$

この空間はコンパクトであることが判明した。さらに、この空間は、関連するグラフオンによって表されるすべての有限グラフの集合を稠密部分集合として含む。これらの観察から、グラフオンの空間は、カット距離に関するグラフの空間の完備化であることが示される。このことから、直接的な帰結として以下が導かれる。

系 1.すべての実数 に対して、 となる整数 が存在し、すべてのグラフオン に対して、最大で個の頂点を持つグラフ が存在する。 ${\displaystyle \varepsilon >0}$ ${\displaystyle N}$ ${\displaystyle W}$ ${\displaystyle G}$ ${\displaystyle N}$ ${\displaystyle \delta _{\square }(W,W_{G})<\varepsilon }$

理由を理解するために、グラフの集合を とします。各グラフに対して、となるすべてのグラフオンを含む開球を考えます。すべてのグラフの開球の集合は を覆うので、コンパクト性は、ある有限部分集合 に対して有限部分被覆が存在することを意味します。ここで、 は内のグラフの中で頂点の最大数であるとみなすことができます。 ${\displaystyle {\mathcal {G}}}$ ${\displaystyle G\in {\mathcal {G}}}$ ${\displaystyle B_{\square }(G,\varepsilon )}$ ${\displaystyle W}$ ${\displaystyle \delta _{\square }(W,W_{G})<\varepsilon }$ ${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$ ${\displaystyle \{B_{\square }(G,\varepsilon )\mid G\in {\mathcal {G}}_{0}\}}$ ${\displaystyle {\mathcal {G}}_{0}\subset {\mathcal {G}}}$ ${\displaystyle N}$ ${\displaystyle {\mathcal {G}}_{0}}$

応用

正則性補題

グラフオン空間のコンパクト性は、セメレディの正則性補題の解析的定式化と考えることができます。実際、元の補題よりも強い結果です。^[9] セメレディの正則性補題は、グラフオンの言語に次のように翻訳できます。ステップ関数を区分的に定数であるグラフオン、つまりのある分割に対してがすべての に対してで定数であるグラフオンと定義します。グラフに正則性分割があるという主張は、それに関連するグラフオンがステップ関数に近いと 言うことと同等です${\displaystyle ({\widetilde {\mathcal {W}}}_{0},\delta _{\square })}$ ${\displaystyle W}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle [0,1]}$ ${\displaystyle W}$ ${\displaystyle S\times T}$ ${\displaystyle S,T\in {\mathcal {P}}}$ ${\displaystyle G}$ ${\displaystyle W_{G}}$

コンパクト性の証明には、弱正則性補題のみが必要です。

グラフオンの弱正則性補題。任意のグラフオンとに対して、最大ステップ数を持つステップ関数が存在し、となる。 ${\displaystyle W}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle W'}$ ${\displaystyle \lceil 4^{1/\varepsilon ^{2}}\rceil }$ ${\displaystyle \lVert W-W'\rVert _{\square }\leq \varepsilon }$

しかし、これは強い正則性補題のようなより強い正則性の結果を証明するために使うことができます。

グラフオンの強い正則性補題。任意の正の実数列に対して、任意のグラフオンに対して、グラフオンと、ステップ関数が存在し、そのステップは、${\displaystyle \mathbf {\varepsilon } =(\varepsilon _{0},\varepsilon _{1},\dots )}$ ${\displaystyle S}$ ${\displaystyle W}$ ${\displaystyle W'}$ ${\displaystyle U}$ ${\displaystyle k<S}$ ${\displaystyle \lVert W-W'\rVert _{1}\leq \varepsilon _{0}}$ ${\displaystyle \lVert W'-U\rVert _{\square }\leq \varepsilon _{k}.}$

強正則性補題の証明は、上記の系1と概念的に類似しています。すべてのグラフンはノルムのステップ関数で近似でき、球体の集合がを覆うことが示されます。これらの集合は計量的には開集合ではありませんが、わずかに拡大することで開集合になります。ここで有限部分被覆を取り、望ましい条件が満たされることを示すことができます。 ${\displaystyle W}$ ${\displaystyle U}$ ${\displaystyle L_{1}}$ ${\displaystyle B_{1}(U,\varepsilon _{0})}$ ${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$ ${\displaystyle \delta _{\square }}$

シドレンコ予想

グラフンの解析的性質により、準同型に関連する不等式をより柔軟に解析することができます

例えば、シドレンコ予想は極値グラフ理論における主要な未解決問題であり、平均次数（ある に対して）の頂点 上の任意のグラフと、頂点および辺 上の二部グラフについて、からへの準同型写像の数は少なくとも であると主張する。^[10]この量はランダムグラフ における のラベル付きサブグラフの期待数であるため、この予想は、任意の二部グラフ に対して、ランダムグラフは（期待値として）ある固定の辺密度を持つすべてのグラフ上で のコピー数が最小になるという主張として解釈できる。${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle pn}$ ${\displaystyle p\in [0,1]}$ ${\displaystyle H}$ ${\displaystyle v}$ ${\displaystyle e}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle p^{e}n^{v}}$ ${\displaystyle H}$ ${\displaystyle G(n,p)}$ ${\displaystyle H}$ ${\displaystyle H}$

シドレンコ予想に対する多くのアプローチは、問題をグラフオン上の積分不等式として定式化し、それによって他の解析的アプローチを用いて問題を解くことを可能にする。^[11]

一般化

グラフォンは、自然と稠密な単純グラフに関連付けられます。このモデルには、装飾グラフォンと呼ばれることが多い、稠密な有向重み付きグラフへの拡張があります。^{[12]また、ランダムグラフモデル[13]}とグラフ極限理論^{[14] [15]}の両方の観点から、スパースグラフ領域への最近の拡張もあります

参考文献

1. Orbanz, P.; Roy, ​​DM (2015). 「グラフ、配列、およびその他の交換可能なランダム構造のベイズモデル」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 37 (2): 437–461 . arXiv : 1312.7857 . Bibcode :2015ITPAM..37..437O. doi :10.1109/tpami.2014.2334607. PMID  26353253. S2CID  566759
2. Wolfe, Patrick J.; Olhede, Sofia C. (2013-09-23). 「ノンパラメトリックグラフオン推定」. arXiv : 1309.5936 [math.ST].
3. Choi, David; Wolfe, Patrick J. (2014年2月). 「個別に交換可能なネットワークデータの共クラスタリング」. The Annals of Statistics . 42 (1): 29– 63. arXiv : 1212.4093 . doi :10.1214/13-AOS1173. ISSN  0090-5364. S2CID  16291079.
4. Gao, Chao; Lu, Yu; Zhou, Harrison H. (2015年12月). 「レート最適グラフオン推定」. The Annals of Statistics . 43 (6): 2624– 2652. arXiv : 1410.5837 . doi :10.1214/15-AOS1354. ISSN  0090-5364. S2CID  14267617.
5. Yuan, Zhang; Elizaveta, Levina; Ji, Zhu (2017). 「近傍平滑化によるネットワークエッジ確率の推定」 . Biometrika . 104 (4): 771– 783. doi :10.1093/biomet/asx042. ISSN  0006-3444.
6. Lovász, L.大規模ネットワークとグラフの限界。アメリカ数学会。
7. Chung, Fan RK ; Graham, Ronald L. ; Wilson, RM (1989). 「準ランダムグラフ」. Combinatorica . 9 (4): 345– 362. doi : 10.1007/BF02125347 .
8. Glasscock, D. (2015). 「グラフオンとは何か」.アメリカ数学会報. 62 (1): 46– 48. arXiv : 1611.00718 .
9. ロヴァシュ、ラズロ;セゲディ、バラーズ (2007)。 「分析者のためのシェメレディの補題」。幾何学的および機能的分析。17 : 252–270。土井:10.1007/s00039-007-0599-6。S2CID  15201345。
10. Sidorenko, A. (1993). 「二部グラフの相関不等式」.グラフと組合せ論. 9 ( 2–4 ): 201– 204. doi :10.1007/BF02988307.
11. Hatami, H. (2010). 「グラフノルムとシドレンコ予想」.イスラエル数学ジャーナル. 175 (1): 125– 150. arXiv : 0806.0047 . doi :10.1007/s11856-010-0005-1.
12. アンドレアス、ハウプト;シュルツ、トーマス。ハタミ、モハメッド。トラン、ゴック（2020年7月17日）。 「大規模ネットワーク上の分類: モチーフとグラフォンによる定量的境界 (研究)」。バハール州アクーにて。ダニアーリ、ドナテッラ。レウィッカ、マルタ。パティ、アラティ。 RV、サラスワシー;テボー＝ユンケム、ミランダ（編）。数理科学の進歩。女性数学協会シリーズ。 Vol. 21. スプリンガー、チャム。ページ 107–126。arXiv : 1710.08878。土井: 10.1007/978-3-030-42687-3_7。ISBN 978-3-030-42687-3。
13. Veitch, V.; Roy, ​​DM (2015). 「交換可能なランダム測度から生じるランダムグラフのクラス」arXiv : 1512.03099 [math.ST]
14. Borgs, C.; Chayes, JT; Cohn, H.; Zhao, Y. (2019). 「疎グラフ収束のL ^p理論 I：限界、疎ランダムグラフモデル、およびべき乗分布」.アメリカ数学会誌. 372 (5): 3019– 3062. arXiv : 1401.2906 . doi :10.1090/tran/7543. S2CID  50704206.
15. Borgs, C.; Chayes, JT; Cohn, H.; Zhao, Y. (2018). 「疎グラフ収束のL ^p理論 II：LD収束、商、右収束」. The Annals of Probability . 46 (2018): 337– 396. arXiv : 1408.0744 . doi :10.1214/17-AOP1187. S2CID  51786393.