ギルバートモデル
定義 1 2
簡単な定義
リンクがそれぞれ独立に確率 $p \in [0,1]$ に従って接続されるシンプルネットワークのランダムネットワークを、ギルバートモデルgilbert model $\mathbb{G}_{n,p}$ と呼ぶ。
難しい定義
確率空間 $( \Omega , \mathcal{F} , P)$ が与えられ、$n$ 個のラベル付けされたlabeledノードを持つネットワークのプロパティ $2^{\binom{n}{2}} \subseteq 2^{\binom{n}{2}}$ があるとする。リンクの数 $0 \le m \le \binom{n}{2}$ に対して、次の確率質量関数を持つ$\mathcal{F}$-可測関数 $\mathbb{G}_{n,p} : \Omega \to 2^{\binom{n}{2}}$ をギルバートモデルと呼ぶ。 $$ P \left( \mathbb{G}_{n,p} = G \right) = p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} \qquad , \forall G \in \mathscr{G}_{n,m} \subset 2^{\binom{n}{2}} $$
説明
ギルバートモデルはエルデシュ–レーニモデル (ERモデル)とともに多くの文献で言及されているが、実際にはERモデルと言いながらギルバートモデルを使用していることが非常に多い。両モデル間に違いがないわけではない。実際に深く掘り下げると、完全に違うモデルで、分厚い本一冊が出るほどだが、特に応用ネットワーク理論の文脈ではこれらをERモデルとしてひとくくりにする傾向が強い。一般的には使われない表現だが、確率分布が二項分布であるという意味で二項ランダムネットワークbinomial Random Networkとも呼べる。
$\mathbb{G}_{n,p}$ は大体 $\displaystyle m = \binom{n}{2} p \approx {{ n^{2} p } \over { 2 }}$ 個くらいのリンクを持つと予想される。ERモデルがちょうど $m$ 個のリンクを持つのと違い、ギルバートモデルはネットワークの大きさに係数 $p$ に比例するだけでリンクの数が定まっているわけではない。
定義は難しく書かれているから難しそうに見えるが、アルゴリズムを読んでみると実は簡単だ。ギルバートモデルでネットワークをサンプリングするアルゴリズムは以下の通り。
アルゴリズム
入力
ノードの数$n \in \mathbb{N}$とリンク確率$p \in \left( 0, 1 \right)$が与えられているとする。
ステップ1. 初期化
$n$個のノードを持つヌルグラフ $G$ を作る。
ステップ2. ベルヌーイ試行
for $i = 1 , \cdots , n$
for $j = 1 , \cdots , n$
if $i \ne j$
$p$ の確率で次のようにネットワーク $G$ にリンク $ij$ を追加する。$$G \gets G + ij$$
出力
ノードが$n$個でリンクが$m \approx n^{2} p / 2$個くらいあるシンプルグラフ$G \in 2^{\binom{n}{2}}$を得る。
性質
- [1]: ギルバートモデル $\mathbb{G}_{n,p}$ からサンプリングされたネットワークのリンク数が正確に $m$ である必要がある場合は、$\mathbb{G}_{n,m}$ からサンプリングされたものと同じである。
- [2] 度数分布: $\lambda = np$ のとき、$n \to \infty$ で各ノードの度数はポアソン分布 $\displaystyle \text{Poi} \left( np \right)$ に収束する。 $$ P \left( \deg v = k \right) \to {{ e^{-\lambda} \lambda^{k} } \over { k! }} \qquad , \lambda \approx np $$
証明
[1]
エルデシュ-レーニモデル: 次のような確率質量関数を持つランダムグラフをエルデシュ–レーニグラフerdős–Rényi Graph $\mathbb{G}_{n,m}$ と呼ぶ。 $$ P \left( \mathbb{G}_{n,m} = G \right) = \binom{\binom{n}{2}}{m}^{-1} \qquad , \forall G \in \mathscr{G}_{n,m} $$
Claim: 任意の$G_{0} \in \mathscr{G}_{n,m}$を考えた時、次を示せば良い。 $$ P \left( \mathbb{G}_{n,p} = G_{0} | \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) = \binom{\binom{n}{2}}{m}^{-1} $$
$\mathbb{G}_{n,p}$が正確に$G_{0}$であるよりも$\mathbb{G}_{n,p} \in \mathscr{G}_{n,m}$である可能性、つまりギルバートモデルでサンプリングしたけれども、リンクが全部で$m$個である可能性の方が大きい。これを事件として表すと $$ \begin{align*} \left\{ \mathbb{G}_{n,p} = G_{0} \right\} & \subset \left\{ \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right\} \\ \implies \left\{ \mathbb{G}_{n,p} = G_{0} \right\} & \cap \left\{ \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right\} = \left\{ \mathbb{G}_{n,p} = G_{0} \right\} \qquad \cdots (\star) \end{align*} $$ ここで、各確率を計算すると$\displaystyle P \left( \mathbb{G}_{n,p} = G_{0} \right) = p^{m} \left( 1 - p \right)^{\binom{n}{2} - m}$であるため、 $$ \begin{align*} & P \left( \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) \\ =& P \left( \bigcup_{G \in \mathscr{G}_{n,m}} \left\{ \mathbb{G}_{n,p} = G \right\} \right) \\ =& \sum_{G \in \mathscr{G}_{n,m}} P \left( \mathbb{G}_{n,p} = G \right) \\ =& \binom{\binom{n}{2}}{m} p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} \end{align*} $$ である。これで条件付き確率を計算すると、 $$ \begin{align*} P \left( \mathbb{G}_{n,p} = G_{0} | \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) =& {{ P \left( \mathbb{G}_{n,p} = G_{0} \land \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) } \over { P \left( \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) }} \\ =& {{ P \left( \mathbb{G}_{n,p} = G_{0} \right) } \over { P \left( \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) }} & \because (\star) \\ =& {{ p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} } \over { \binom{\binom{n}{2}}{m} p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} }} \\ =& \binom{\binom{n}{2}}{m}^{-1} \end{align*} $$ を示すことができる。ここで、$\land$は論理積である。
[2]
$n$個のノードが与えられ、各ノードが接続される確率$p$が与えられており、ノードの度数は残り$(n-1)$個の他のノードと接続されているかどうかに依るので、二項分布 $B(n-1,p)$に従うことになる。数式できれいに書くと、次のようになる。 $$ P \left( \deg v = k \right) = \binom{n-1}{k} p^{k} \left( 1 - p \right)^{n-1-k} $$
二項分布の極限分布としてのポアソン分布: $X_{n} \sim B(n,p)$とする。
$\lambda \approx np$ならば、 $$ X_{n} \overset{D}{\to} \text{Poi} (\lambda) $$
この補題により、十分に大きいギルバートネットワークのノードの度数はポアソン分布に従う。
■
可視化
$n = 50$, $p = 12\%$ の時にサンプリングされたERネットワークとそのノードの度数のヒストグラムである。
コード
JuliaのGraphs, GraphRecipes パッケージを使用したコード。
cd(@__DIR__); pwd()
@time using Graphs
@time using Plots
@time using GraphRecipes
n = 50
G_np = erdos_renyi(n, 6/n, seed = 0)
plot_G_np = graphplot(G_np, title = "n = 50, p = 12%", curves=false, size = (300,300), node_weights = degree(G_np).^2,
node_shape = :rect, nodecolor = :black, nodestrokealpha = 0.5, edgecolor = :black)
png(plot_G_np, "plot_G_np.png")
histogram_G_np = histogram(degree(G_np), title = "Histogram of Degree",
color = :black, alpha = 0.8, label = :none, size = (300,300))
png(histogram_G_np, "histogram_G_np.png")