この記事の概要
私は、任意の特徴量を持ったグラフを生成する研究に携わっています。現在のグラフ生成の研究では、Deep Leaningを用いるのが一般的です。しかし、Deep Learningが主流になる以前は、何らかのアルゴリズム(ERモデル、RSモデル、BAモデルなど)によって任意の特徴量を持つグラフを生成していました。この記事では、最も単純な統計的グラフ生成モデルであるErdös-Rényi(ER)モデルが持つ特徴を数式を交えて説明します。
Erdös-Rényi（ER)モデルとは
1959年に提案されたErdös-Rényi(ER)モデル[5]は最も原始的なグラフ生成モデルです。このモデルは、与えられたノード間に一定確率でエッジを張るというシンプルなアルゴリズムで構成されます。ERモデルは、ノード数nとノード間にエッジを張る確率pをパラメータにもちます。従って、ERモデルによって生成されるグラフをG_{ER}(n,p)と表すことにします。このグラフは、ランダムにエッジを張るため特別なノードが存在しないという特徴があります。
平均次数
G_{ER}(n,p)の平均次数\bar{d}は、次のように表されます。
\bar{d}=\sum_{d=0}^{n}d\cdot{}_{n-1}C_d\cdot p^d(1-p)^{n-1-d}=(n-1)p
計算方法
次数とは、あるノードvに接続されているエッジの本数のことです。まず、平均次数を求める前にあるノードvが次数dである確率を考えます。
- ノードvの次数がdである時、自分以外のn-1個のノードからd個のノードを選択したことになります。従って、{}_{n-1}C_dです。
-
d個のノードと接続される確率は、p^dであり、n-1-d個のノードと接続されない確率は、(1-p)^{n-1-d}です。
従って、ノードvの次数がdである確率は、次のように表せます。
P(deg(v)=d)={}_{n-1}C_d\cdot p^d(1-p)^{n-1-d}\quad(1)
ここで、deg()は、ノードvの次数を返す関数です。
上の確率を用いて、平均次数は期待値として計算することができます。平均次数を\bar{d}で表すことにすると、
\bar{d}=\sum_{d=0}^{n}d\cdot{}_{n-1}C_d\cdot p^d(1-p)^{n-1-d}\quad(2)
と表せます。ここで、確率p及びq(=1-p)を用いた二項定理を考えます。
(p+q)^{n-1}=\sum_{d=0}^{n}{}_{n-1}C_d\cdot p^dq^{n-1-d}
両辺をpで微分すると、
(n-1)(p+q)^{n-2}=\sum_{d=0}^{n}d \cdot{}_{n-1}C_d\cdot p^{d-1}q^{n-1-d}
(n-1)(p+q)^{n-2}=\frac{1}{p}\sum_{d=0}^{n}d \cdot{}_{n-1}C_d\cdot p^{d}q^{n-1-d}
となります。ここで、q=1-pを代入すると
(n-1)(p+(1-p))^{n-2}=\frac{1}{p}\sum_{d=0}^{n}d \cdot{}_{n-1}C_d\cdot p^{d}(1-p)^{n-1-d}
(n-1)p=\sum_{d=0}^{n}{}_{n-1}C_d\cdot d \cdot p^{d}(1-p)^{n-1-d}
となります。右辺が(2)式で示した\bar{d}の式と一致するので証明終了です。
クラスタ係数
G_{ER}(n,p)のノードvのクラスタ係数C(v)は、次のように表されます。
C(v)=\frac{p\times\frac{1}{2}deg(v)(deg(v)-1)}{\frac{1}{2}deg(v)(deg(v)-1)}=p=\frac{\bar{d}}{n-1}
ここで、C(),deg()はノードvのクラスタ係数及び次数を返す関数とします。
計算方法
クラスタ係数とは、ノードv毎に定まる値です。ノードvのクラスタ係数を返す関数をC()とします。クラスタ係数は、ノードvに接続しているノード同士がどれくらい互いに接続し合っているかを表す値です。以下のように考えます。
- ノードvに接続されているノード数はdeg(v)で表されます。
-
deg(v)個のノードが互いに接続する組み合わせは、{}_{deg(v)}C_2なので、全ての組み合わせは次のように表されます。
\frac{1}{2}deg(v)(deg(v)-1)
確率pでエッジは張られるので、実際に張られるエッジの本数は、
p\times\frac{1}{2}deg(v)(deg(v)-1)
と表されます。これらの比からクラスタ係数を計算することができます。
次数分布
ノード数nが十分に大きい時、平均次数\bar{d}は一定値に近づくことが知られています。従って、次のような仮定をおきます。
n\to\infty\Rightarrow(n-1)p=\lambda,\quad(\lambda:const.)
この時、G_{ER}(n,p)の次数をdとして次数分布P_{d}は、次のように表されます。また、nが十分に大きい時、この分布はポアソン分布に従います。
P_{d}={}_{n-1}C_d\cdot p^d(1-p)^{n-1-d}\sim\frac{\lambda^{d}}{d!}e^{-\lambda}
計算方法
次数分布とは、次数がdであるようなノードの分布を示したものです。次数分布とは、(1)式で求めた確率の(離散)確率分布として与えられます。従って、次のように表されます。
P_{d}={}_{n-1}C_d\cdot p^d(1-p)^{n-1-d}
n\to\inftyとした時に、ERモデルの次数分布はポアソン分布に従うことを証明します。二項分布の極限がポアソン分布に従うことは、ポアソンの小数の法則として広く知られています。[3]
最初に、次のような式変形を行います。
\begin{aligned}
P_d & =\frac{(n-1) !}{d !(n-1-d) !} p^d(1-p)^{n-1-d} \\
& =\frac{n(n-1) \cdots(n-d) p^d}{d !}\left(1-\frac{\lambda}{n}\right)^{n-1-d}\quad(3)\\
& =\frac{1}{d !} \cdot 1 \cdot\left(1-\frac{1}{n}\right) \cdots\left(1-\frac{d}{n}\right) n^d p^d\left(1-\frac{\lambda}{n-1}\right)^{n-1-d}\quad(4)\\
& =\frac{\lambda^d}{d !} 1 \cdot\left(1-\frac{1}{n}\right) \cdots\left(1-\frac{d}{n}\right) \frac{\left(1-\frac{\lambda}{n-1}\right)^{n-1}}{\left(1-\frac{\lambda}{n-1}\right)^{d}}
\end{aligned}
わかりにくいですが、(3)式から(4)式への変形では、n^dで括っています。また、後で定義しますが\lambda=npとしています。
nが十分に大きい時、平均次数\bar{d}が一定値\lambdaに収束すると仮定します。この仮定の妥当性を現実の対人関係のネットワークに置き換えて考えてみます。世界人口が多少増減したところで一人の人間が付き合える人間の数に変化はありません。従って、十分巨大なネットワークにおいて平均次数\bar{d}が一定値となることを仮定することは妥当であると考えられます。
仮定より、\lambda=(n-1)p=const.として、n\to\inftyとすることを考えます。
\begin{aligned}
& \lim _{n \rightarrow \infty} 1 \cdot\left(1-\frac{1}{n}\right) \cdots\left(1-\frac{d}{n}\right)=1 \\
& \lim _{n \rightarrow \infty}\left(1-\frac{\lambda}{(n-1)}\right)^{d}=1
\end{aligned}
となります。ネイピア数の定義より、
e\equiv\lim _{x \rightarrow \pm \infty}\left(1+\frac{1}{x}\right)^x
なので、
\begin{aligned}
& \lim _{n \rightarrow \infty}\left(1-\frac{\lambda}{n-1}\right)^{n-1}=\lim _{n \rightarrow \infty}\left\{\left(1-\frac{\lambda}{n-1}\right)^{-(n-1)/\lambda}\right\}^{-\lambda} \\
& =\lim _{x \rightarrow-\infty}\left\{\left(1+\frac{1}{x}\right)^x\right\}^{-\lambda}\left(x=-\frac{n-1}{\lambda}\right) \\
& =e^{-\lambda}
\end{aligned}
となります。従って、まとめると
\lim_{n\to\infty}P_d=\frac{\lambda^d}{d !}e^{-\lambda}
となり証明終了です。
参考
Discussion