ランダムグラフ

• ランダムグラフ
  • Erdős–Rényiグラフ
  • ランダム正則グラフ

ランダムグラフとはその名の通り、ランダムに生成されたグラフであり、その分布をランダムグラフモデルと呼ぶ。

Erdős–Rényiグラフ

Erdős–Rényiグラフとは最も基本的なランダムグラフで、各頂点のペアそれぞれに対し独立にコイントスを行い、その結果に応じて辺で結んで得られるランダムグラフである。

定義 (Erdős–Rényiグラフ).

パラメータ$n\in\Nat$、$p\in[0,1]$に対し、Erdős–Rényiグラフとは頂点集合が$[n]= \{1,\dots,n\}$で 各頂点ペアを独立に同じ確率$p$で辺で結んで得られるランダムなグラフで、そのようなランダムグラフの分布を$\mathcal{G}(n,p)$と表す。すなわち $\calG(n,p)$とは

\[\begin{align*} \Pr_{G\sim \mathcal{G}(n,p)}[G=H] = p^{|E(H)|}\cdot (1-p)^{\binom{n}{2} - |E(H)|} \tag{1} \end{align*}\]

によって定まる$n$頂点グラフ上の分布である。

特に$p=1/2$のとき、式(1)の右辺は$H$に依存しない値になるので、$G(n,1/2)$は$n$頂点グラフ全体の集合から一様ランダムに選ばれたグラフとなる。

ランダム正則グラフ

ランダム正則グラフとは次数を固定したときの一様ランダムな正則グラフである。 正則グラフとは全ての頂点の次数が等しいグラフのことを意味し、特にその次数が$d$に等しいグラフを$d$-正則と呼ぶ。

定義 (ランダム正則グラフ).

パラメータ$n,d\in\Nat$（ただし$nd$は偶数）に対してランダム$d$-正則グラフ$G_{n,d}$とは、$n$頂点$d$-正則グラフ全体の中から一様ランダムに選ばれたグラフであり、その分布を$\calG_{n,d}$で表す。