ギルバートモデル
📂グラフ理論 ギルバートモデル 定義 簡単な定義 リンクがそれぞれ独立に確率 p ∈ [ 0 , 1 ] p \in [0,1] p ∈ [ 0 , 1 ] シンプルネットワーク のランダムネットワーク を、ギルバートモデル gilbert model G n , p \mathbb{G}_{n,p} G n , p
難しい定義 確率空間 ( Ω , F , P ) ( \Omega , \mathcal{F} , P) ( Ω , F , P ) n n n labeled ノードを持つネットワークのプロパティ 2 ( n 2 ) ⊆ 2 ( n 2 ) 2^{\binom{n}{2}} \subseteq 2^{\binom{n}{2}} 2 ( 2 n ) ⊆ 2 ( 2 n ) 0 ≤ m ≤ ( n 2 ) 0 \le m \le \binom{n}{2} 0 ≤ m ≤ ( 2 n ) 確率質量関数 を持つF \mathcal{F} F G n , p : Ω → 2 ( n 2 ) \mathbb{G}_{n,p} : \Omega \to 2^{\binom{n}{2}} G n , p : Ω → 2 ( 2 n ) ギルバートモデル と呼ぶ。
P ( G n , p = G ) = p m ( 1 − p ) ( n 2 ) − m , ∀ G ∈ G n , m ⊂ 2 ( 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}}
P ( G n , p = G ) = p m ( 1 − p ) ( 2 n ) − m , ∀ G ∈ G n , m ⊂ 2 ( 2 n )
説明 ギルバートモデルはエルデシュ–レーニモデル (ERモデル) とともに多くの文献で言及されているが、実際にはERモデルと言いながらギルバートモデル を使用していることが非常に多い。両モデル間に違いがないわけではない。実際に深く掘り下げると、完全に違うモデルで、分厚い本一冊が出るほどだが、特に応用ネットワーク理論の文脈ではこれらをERモデルとしてひとくくりにする傾向が強い。一般的には使われない表現だが、確率分布が二項分布 であるという意味で二項ランダムネットワーク binomial Random Network とも呼べる。
G n , p \mathbb{G}_{n,p} G n , p m = ( n 2 ) p ≈ n 2 p 2 \displaystyle m = \binom{n}{2} p \approx {{ n^{2} p } \over { 2 }} m = ( 2 n ) p ≈ 2 n 2 p m m m ギルバートモデル はネットワークの大きさに係数 p p p
定義は難しく書かれているから難しそうに見えるが、アルゴリズムを読んでみると実は簡単だ。ギルバートモデル でネットワークをサンプリングするアルゴリズムは以下の通り。
アルゴリズム 入力
ノードの数n ∈ N n \in \mathbb{N} n ∈ N p ∈ ( 0 , 1 ) p \in \left( 0, 1 \right) p ∈ ( 0 , 1 )
ステップ1. 初期化
n n n ヌルグラフ G G G
ステップ2. ベルヌーイ試行
for i = 1 , ⋯ , n i = 1 , \cdots , n i = 1 , ⋯ , n j = 1 , ⋯ , n j = 1 , \cdots , n j = 1 , ⋯ , n i ≠ j i \ne j i = j p p p G G G i j ij ij G ← G + i j G \gets G + ij G ← G + ij
出力
ノードがn n n m ≈ n 2 p / 2 m \approx n^{2} p / 2 m ≈ n 2 p /2 G ∈ 2 ( n 2 ) G \in 2^{\binom{n}{2}} G ∈ 2 ( 2 n )
性質 [1]: ギルバートモデル G n , p \mathbb{G}_{n,p} G n , p m m m G n , m \mathbb{G}_{n,m} G n , m [2] 度数分布: λ = n p \lambda = np λ = n p n → ∞ n \to \infty n → ∞ ポアソン分布 Poi ( n p ) \displaystyle \text{Poi} \left( np \right) Poi ( n p ) P ( deg v = k ) → e − λ λ k k ! , λ ≈ n p
P \left( \deg v = k \right) \to {{ e^{-\lambda} \lambda^{k} } \over { k! }} \qquad , \lambda \approx np
P ( deg v = k ) → k ! e − λ λ k , λ ≈ n p 証明 [1] エルデシュ-レーニモデル : 次のような確率質量関数 を持つランダムグラフ をエルデシュ–レーニグラフ erdős–Rényi graph G n , m \mathbb{G}_{n,m} G n , m P ( G n , m = G ) = ( ( n 2 ) m ) − 1 , ∀ G ∈ 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}
P ( G n , m = G ) = ( m ( 2 n ) ) − 1 , ∀ G ∈ G n , m
Claim: 任意のG 0 ∈ G n , m G_{0} \in \mathscr{G}_{n,m} G 0 ∈ G n , m P ( G n , p = G 0 ∣ G n , p ∈ G n , m ) = ( ( n 2 ) m ) − 1
P \left( \mathbb{G}_{n,p} = G_{0} | \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) = \binom{\binom{n}{2}}{m}^{-1}
P ( G n , p = G 0 ∣ G n , p ∈ G n , m ) = ( m ( 2 n ) ) − 1
G n , p \mathbb{G}_{n,p} G n , p G 0 G_{0} G 0 G n , p ∈ G n , m \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} G n , p ∈ G n , m ギルバートモデル でサンプリングしたけれども、リンクが全部でm m m { G n , p = G 0 } ⊂ { G n , p ∈ G n , m } ⟹ { G n , p = G 0 } ∩ { G n , p ∈ G n , m } = { G n , p = G 0 } ⋯ ( ⋆ )
\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*}
{ G n , p = G 0 } ⟹ { G n , p = G 0 } ⊂ { G n , p ∈ G n , m } ∩ { G n , p ∈ G n , m } = { G n , p = G 0 } ⋯ ( ⋆ ) P ( G n , p = G 0 ) = p m ( 1 − p ) ( n 2 ) − m \displaystyle P \left( \mathbb{G}_{n,p} = G_{0} \right) = p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} P ( G n , p = G 0 ) = p m ( 1 − p ) ( 2 n ) − m P ( G n , p ∈ G n , m ) = P ( ⋃ G ∈ G n , m { G n , p = G } ) = ∑ G ∈ G n , m P ( G n , p = G ) = ( ( n 2 ) m ) p m ( 1 − p ) ( 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*}
= = = P ( G n , p ∈ G n , m ) P G ∈ G n , m ⋃ { G n , p = G } G ∈ G n , m ∑ P ( G n , p = G ) ( m ( 2 n ) ) p m ( 1 − p ) ( 2 n ) − m P ( G n , p = G 0 ∣ G n , p ∈ G n , m ) = P ( G n , p = G 0 ∧ G n , p ∈ G n , m ) P ( G n , p ∈ G n , m ) = P ( G n , p = G 0 ) P ( G n , p ∈ G n , m ) ∵ ( ⋆ ) = p m ( 1 − p ) ( n 2 ) − m ( ( n 2 ) m ) p m ( 1 − p ) ( n 2 ) − m = ( ( n 2 ) m ) − 1
\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*}
P ( G n , p = G 0 ∣ G n , p ∈ G n , m ) = = = = P ( G n , p ∈ G n , m ) P ( G n , p = G 0 ∧ G n , p ∈ G n , m ) P ( G n , p ∈ G n , m ) P ( G n , p = G 0 ) ( m ( 2 n ) ) p m ( 1 − p ) ( 2 n ) − m p m ( 1 − p ) ( 2 n ) − m ( m ( 2 n ) ) − 1 ∵ ( ⋆ ) ∧ \land ∧ 論理積 である。
[2] n n n p p p ( n − 1 ) (n-1) ( n − 1 ) 二項分布 B ( n − 1 , p ) B(n-1,p) B ( n − 1 , p ) P ( deg v = k ) = ( n − 1 k ) p k ( 1 − p ) n − 1 − k
P \left( \deg v = k \right) = \binom{n-1}{k} p^{k} \left( 1 - p \right)^{n-1-k}
P ( deg v = k ) = ( k n − 1 ) p k ( 1 − p ) n − 1 − k
二項分布の極限分布としてのポアソン分布 : X n ∼ B ( n , p ) X_{n} \sim B(n,p) X n ∼ B ( n , p )
λ ≈ n p \lambda \approx np λ ≈ n p X n → D Poi ( λ )
X_{n} \overset{D}{\to} \text{Poi} (\lambda)
X n → D Poi ( λ )
この補題により、十分に大きいギルバートネットワークのノードの度数はポアソン分布に従う。
■
可視化 n = 50 n = 50 n = 50 p = 12 % p = 12\% p = 12%
コード 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" )
一般化 
