ランダムグラフ

数学において、ランダムグラフはグラフ上の確率分布を指す一般的な用語である。ランダムグラフは、単純に確率分布で記述することも、ランダムなプロセスによって記述することもできる。^{[1] [2]}ランダムグラフの理論は、グラフ理論と確率論の交差点に位置する。数学的観点からは、ランダムグラフは典型的なグラフの特性に関する質問に答えるために使用される。その実際的な応用は、複雑なネットワークをモデル化する必要があるすべての分野で見られる。そのため、さまざまな分野で遭遇する多様なタイプの複雑なネットワークを反映して、多くのランダムグラフモデルが知られている。数学的な文脈では、ランダムグラフはほとんど排他的にエルデシュ・レーニのランダムグラフモデルを指す。他の文脈では、どのグラフモデルもランダムグラフと呼ばれることがある。

ランダムグラフは、 n 個の孤立した頂点の集合から始めて、それらの間に連続する辺をランダムに追加することで得られる。この分野の研究の目的は、グラフの特定の特性がどの段階で発生する可能性があるかを判断することである。^[3]異なるランダムグラフモデルは、グラフ上で異なる確率分布を生成する。最も一般的に研究されているのは、エドガー・ギルバートによって提案されたモデルだが、エルデシュ・レーニイモデルと呼ばれることも多く、 G ( n , p )と表記される。このモデルでは、すべての可能な辺は、確率 0 < p < 1で独立して発生する。m個の辺を持つ特定のランダムグラフが得られる確率は、表記 で表される。^[4]${\displaystyle p^{m}(1-p)^{N-m}}$${\displaystyle N={\tbinom {n}{2}}}$

密接に関連するモデルは、エルデシュ・レーニモデルとも呼ばれ、G ( n , M ) と表記され、ちょうどM個のエッジを持つすべてのグラフに等しい確率を割り当てます。0 ≤ M ≤ Nの場合、G ( n , M ) には要素があり、すべての要素は確率で発生します。^[3] G ( n , M ) モデルは、ランダムグラフプロセスの特定の時間 ( M )でのスナップショットとして見ることができます。ランダムグラフプロセスは、n個の頂点とエッジのない状態で始まり、各ステップで、欠落しているエッジのセットから一様に選択された 1 つの新しいエッジを追加する確率過程です。 ${\displaystyle {\tbinom {N}{M}}}$${\displaystyle 1/{\tbinom {N}{M}}}$ ${\displaystyle {\tilde {G}}_{n}}$

代わりに、頂点の無限集合から始めて、すべての可能な辺が確率 0 < p < 1 で独立して発生するようにすると、無限ランダム グラフと呼ばれるオブジェクトGが得られます。p が 0 または 1 であるような些細な場合を除き、このようなG はほぼ確実に次の特性を持ちます。

任意のn + m個の要素が与えられた場合、 Vにはのそれぞれに隣接し、 のいずれにも隣接しない頂点cが存在します。${\displaystyle a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V}$${\displaystyle a_{1},\ldots ,a_{n}}$${\displaystyle b_{1},\ldots ,b_{m}}$

頂点集合が可算である場合、同型性を除いて 、この特性を持つグラフは 1 つだけ、つまりRado グラフしか存在しないことがわかります。したがって、可算無限ランダム グラフはほぼ確実に Rado グラフであり、このため、単にランダム グラフと呼ばれることもあります。ただし、同様の結果は非可算グラフには当てはまりません。非可算グラフには、上記特性を満たす (非同型の) グラフが多数存在します。

ギルバートのランダム グラフ モデルを一般化した別のモデルは、ランダム ドット積モデルです。ランダム ドット積グラフは、各頂点に実数ベクトルを関連付けます。任意の頂点uとv間のエッジuvの確率は、それぞれのベクトルの ドット積u • vの関数です。

ネットワーク確率マトリックスは、エッジ確率を通じてランダム グラフをモデル化します。エッジ確率は、指定された期間に特定のエッジが存在する確率を表します。このモデルは、有向グラフと無向グラフ、重み付きグラフと重みなしグラフ、静的グラフと動的グラフの構造に拡張可能です。 ${\displaystyle p_{i,j}}$${\displaystyle e_{i,j}}$

M≃pN（Nは可能な最大辺数）の場合、最も広く使用されている2つのモデルG ( n , M )とG ( n , p )はほぼ互換性がある。^[5]

ランダム正規グラフは、一般的なランダムグラフとは異なる特性を持つ特殊なケースを形成します。

ランダムグラフのモデルができたら、グラフ上のすべての関数はランダム変数になります。このモデルの研究は、ある特性が発生するかどうか、あるいは少なくとも発生する確率を推定することです。^[4]

ランダムグラフの文脈における「ほぼすべての」という用語は、エラー確率がゼロに近づくような空間と確率のシーケンスを指します。^[4]

ランダム グラフの理論では、ランダム グラフの典型的な特性、つまり特定の分布から抽出されたグラフに高い確率で当てはまる特性を研究します。たとえば、 の特定の値とが連結されている確率を尋ねることがあります。このような質問を研究する際、研究者はランダム グラフの漸近挙動、つまり が非常に大きくなるにつれてさまざまな確率が収束する値に集中することがよくあります。パーコレーション理論は、ランダム グラフ、特に無限大のグラフの連結性を特徴付けます。 ${\displaystyle n}$${\displaystyle p}$${\displaystyle G(n,p)}$${\displaystyle n}$

パーコレーションはグラフ（ネットワークとも呼ばれる）の堅牢性に関連しています。ランダムなノードのグラフと平均次数が与えられます。次に、ノードの一部をランダムに削除し、一部だけを残します。臨界パーコレーションしきい値が存在し、それ以下ではネットワークが断片化しますが、それを超えると巨大な接続コンポーネントが存在します。^{[1] [5] [6] [7] [8]}${\displaystyle n}$${\displaystyle \langle k\rangle }$${\displaystyle 1-p}$${\displaystyle p}$${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$${\displaystyle p_{c}}$

局所的浸透とは、ネットワークからノードの一部が削除されるまで、ノードの隣接ノード、次に近い隣接ノードなどを削除することを指します。ポアソン分布の次数を持つランダム グラフの場合、ランダム削除とまったく同じであることが示されました。 ${\displaystyle 1-p}$${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$

ランダム グラフは、特定の特性を持つグラフの存在を証明しようとする確率的手法で広く使用されています。ランダム グラフ上の特性の存在は、多くの場合、セメレディ正則性補題によって、ほぼすべてのグラフ上のその特性の存在を暗示できます。

ランダム正則グラフにおいて、は、およびが自然数、およびが偶数となるような-正則グラフの集合である。^[3]${\displaystyle G(n,r-reg)}$${\displaystyle r}$${\displaystyle r=r(n)}$${\displaystyle n}$${\displaystyle m}$${\displaystyle 3\leq r<n}$${\displaystyle rn=2m}$

グラフの次数列は集合内の辺の数のみに依存する^[3]${\displaystyle G}$${\displaystyle G^{n}}$

${\displaystyle V_{n}^{(2)}=\left\{ij\ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.}$

ランダムグラフの辺が十分に大きく、ほぼすべての辺の次数が少なくとも 1 になることが保証される場合、ほぼすべての辺は連結されており、が偶数の場合、ほぼすべての辺は完全一致を持ちます。特に、ほぼすべてのランダムグラフで最後の孤立した頂点が消えた瞬間、グラフは連結されます。^[3]${\displaystyle M}$${\displaystyle G_{M}}$${\displaystyle G_{M}}$${\displaystyle G_{M}}$${\displaystyle n}$${\displaystyle G_{M}}$

偶数個の頂点を持ち、辺によって最小次数が 1 に上がるグラフ プロセス、または よりわずかに多い辺を持ち確率が 1 に近いランダム グラフでは、最大 1 つの頂点を除いてグラフが完全に一致することが保証されます。 ${\displaystyle {\tfrac {n}{4}}\log(n)}$

ある定数 に対して、頂点と少なくとも個の辺を持つほぼすべてのラベル付きグラフはハミルトンです。確率が 1 に近づくと、最小次数を 2 に増やす特定の辺によってグラフはハミルトンになります。 ${\displaystyle c}$${\displaystyle n}$${\displaystyle cn\log(n)}$

ランダムグラフの特性は、グラフ変換によって変化したり不変のままになったりする。例えば、 Mashaghi A.らは、ランダムグラフをエッジデュアルグラフ（または線グラフ）に変換する変換により、次数分布はほぼ同じだが次数相関と大幅に高いクラスタリング係数を持つグラフのアンサンブルが生成されることを実証した。^[9]

頂点V ( G ) = {1, ..., n }を持つn次ランダムグラフGが与えられた場合、色の数に関する貪欲アルゴリズムによって、頂点は色 1、2、... で着色できます (頂点 1 は色 1、頂点 2 は頂点 1 に隣接していない場合は色 1、そうでない場合は色 2 など)。^[3] q色 の数が与えられた場合のランダムグラフの適切な着色の数は、その彩色多項式と呼ばれ、今のところ不明です。パラメータnと辺の数mまたは接続確率p を持つランダムグラフの彩色多項式のゼロのスケーリングは、記号パターンマッチングに基づくアルゴリズムを使用して経験的に研究されています。^[10]

ランダム ツリーは、確率過程によって形成されるツリーまたは樹木です。 順序nおよびサイズM ( n )のランダム グラフの広範囲で、順序kのツリー コンポーネントの数の分布は、漸近的にポアソン分布になります。 ランダム ツリーの種類には、一様全域木、ランダム最小全域木、ランダム バイナリ ツリー、treap、高速探索ランダム ツリー、ブラウン ツリー、ランダム フォレストなどがあります。

確率空間で定義されたランダム グラフ モデルを考え、を各グラフにm個のプロパティのベクトルを割り当てる実数値関数とします。 が固定されている場合、条件付きランダム グラフは、確率測度が' となるすべてのグラフに 0 の確率を割り当てるモデルです。 ${\displaystyle (\Omega ,{\mathcal {F}},P)}$${\displaystyle {\mathcal {P}}(G):\Omega \rightarrow R^{m}}$${\displaystyle \Omega }$${\displaystyle \mathbf {p} \in R^{m}}$${\displaystyle P}$${\displaystyle {\mathcal {P}}(G)\neq \mathbf {p} }$

特殊なケースは条件付き一様ランダムグラフで、指定されたプロパティを持つすべてのグラフに等しい確率を割り当てます。条件付け情報が必ずしもエッジ数Mではなく、他の任意のグラフプロパティである場合、これらはエルデシュ-レーニモデルG ( n , M ) の一般化として考えることができます。この場合、利用できる分析結果は非常に少なく、平均プロパティの経験的分布を得るにはシミュレーションが必要です。 ${\displaystyle P}$ ${\displaystyle {\mathcal {P}}(G)}$

ランダムグラフモデルの最初の使用は、1938年にヘレン・ホール・ジェニングスとジェイコブ・モレノによって行われたもので、ネットワークデータ内の相互リンクの割合をランダムモデルと比較する研究において「チャンスソシオグラム」（有向エルデシュ・レーニモデル）が検討されました。 ^[11] もう1つの使用法は、「ランダムネット」という名前で、 1951年にレイ・ソロモノフとアナトール・ラポポートによって、固定された出力次数とランダムに選択された他の頂点への接続を持つ有向グラフモデルを使用して行われました。^[12]

ランダム グラフのエルデシュ・レーニ モデルは、 Paul ErdősとAlfréd Rényiが 1959 年の論文「ランダム グラフについて」^[8]で最初に定義し、ギルバートが論文「ランダム グラフ」で独立して定義しました。^[6]

• ボーズ・アインシュタイン凝縮：ネットワーク理論アプローチ
• キャビティ法
• 複雑なネットワーク
• 二段階進化
• エルデシュ・レーニモデル
• 指数ランダムグラフモデル
• グラフ理論
• 相互依存ネットワーク
• ネットワーク科学
• 浸透
• 浸透理論
• ゲル化のランダムグラフ理論
• 通常のグラフ
• スケールフリーネットワーク
• 半線形応答
• 確率的ブロックモデル
• ランシキネッティ – フォルトゥナート – ラディッキ ベンチマーク