📂グラフ理論

エルデシュ＝レーニイモデル

ビルドアップ

$n$個のラベル付けられた頂点と$m$個のエッジを持つシンプルグラフについて、プロパティ$\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$が与えられているとしよう。

正確に$m$個のリンクを持つランダムグラフは$\mathbb{G}_{n, m} : \Omega \to \mathscr{G}_{n,m}$のように表現できる。このように作られるグラフは、$n$個のノードと$m$個のリンクしか持たなければ、誰がどのような確率で作ったとしても関係ない。つまり、まだ確率分布は与えられていない。ここで我々が最も簡単に考えることができる確率分布は、みんなが同じ確率である一様分布だ。

シンプルグラフは異なるノードを接続しなければならないので、$n$個のノードの中から$2$個を選んで$\binom{n}{2}$個のリンクを持つことができ、特に$m$個のリンクを選ぶからには$\displaystyle \left| \mathscr{G}_{n,m} \right| = \binom{\binom{n}{2}}{m}$になる。すべての$G \in \mathscr{G}_{n,m}$に対して $$P \left( \mathbb{G}_{n,m} = G \right) = \binom{\binom{n}{2}}{m}^{-1}$$ とすれば、$n$個のノードと$m$個のリンクを持つすべてのグラフが選ばれる確率が等しいことになる。

定義 ^{1 2}

確率空間 $( \Omega , \mathcal{F} , P)$が与えられ、プロパティ$\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$を考えよう。

以下の確率質量関数を持つランダムグラフをエルデシュ・レーニ・グラフ^{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}$$

説明

エルデシュ・レーニモデルは、ランダムグラフの代表的なネットワークで、科学界全体で頻繁に発見され、使われる。略してERモデルとも呼ばれる。すべての$G \in \mathscr{G}_{n,m}$が選ばれる確率が同じで一様分布に従っているという意味で、ユニフォームランダムネットワークとも呼べる。

ギルバートモデル $\mathbb{G}_{n,p}$は、異なる方法でERモデル $\mathbb{G}_{n,p}$に似たネットワークを構築する。アルゴリズム的にも数学的にも二つのモデルは異なるが、二つのモデルの違いに焦点を当てなければ、実質的にはほぼ同じだ。残念ながらERモデルがあまりにも有名であるため、ギルバートモデルもただERモデルとして話されることが多いが、それは著者がその違いを区別できないか、区別する必要を感じないからだろう、我々もあまりこだわらないようにしよう。

ERネットワークをサンプリングするアルゴリズムは以下の通りだ。

アルゴリズム

入力

ノードの数$n \in \mathbb{N}$とリンクの数$m \in \mathbb{N}$が与えられているとする。

---

ステップ1. 初期化

$n$個のノードを持つヌルグラフ $G$を作り、次のようなタプルのリスト（シーケンス）$\left\{ l_{k} \right\}$を作る。 $$\left\{ l_{k} \right\} = \left\{ (i,j) \in [n]^{2} : i \ne j \right\} \qquad , [n] = \left\{ 1, \cdots , n \right\}$$ シーケンス$\left\{ l_{k} \right\}$の順序をランダムにシャッフルする。

---

ステップ2. サンプリング

for $k = 1 , \cdots , m$

　　$l_{k} = (i,j)$に対して、ネットワーク$G$にリンク$ij$を以下のように加える。 $$G \gets G + ij$$

---

出力

ノードが$n$個でリンクが$m$個のシンプルグラフ$G \in \mathscr{G}_{n,m}$を得る。

可視化

以下は$n = 50$, $m = 150$の時にサンプリングされたERネットワークとそのノードの次数のヒストグラムである。

コード

以下はJuliaのGraphs、GraphRecipesパッケージを使ったコードだ。

cd(@__DIR__); pwd()

@time using Graphs
@time using Plots
@time using GraphRecipes

n = 50
G_nm = erdos_renyi(n, 3n, seed = 0)
plot_G_nm = graphplot(G_nm, title = "n = 50, m = 150", curves=false, size = (300,300), node_weights = degree(G_nm).^2,
 node_shape = :rect, nodecolor = :black, nodestrokealpha = 0.5, edgecolor = :black)
png(plot_G_nm, "plot_G_nm.png")
histogram_G_nm = histogram(degree(G_nm), title = "Histogram of Degree",
 color = :black, alpha = 0.8, label = :none, size = (300,300))
png(histogram_G_nm, "histogram_G_nm.png")