Aritalab:Lecture/NetworkBiology/Erdos-Renyi Model

ここでは頂点がすべて連結した無向グラフを扱う。

歴史

• 1998 D. J. Watts, Steven Strogatz "Collective dynamics of 'small-world' networks". Nature 393: 440–442. doi:10.1038/30918.

クラスター係数と平均頂点間距離

Link Analysisではグラフにおける各頂点の尺度としてcentralityとprestigeを紹介した。ここではネットワーク全体についての尺度としてクラスター係数$C$と平均頂点間距離$L$を紹介する。

クラスター係数

クラスター係数は隣接する頂点間の辺の密度の平均値にあたる。まず各頂点$i$におけるクラスター係数を以下のように定義する。辺の長さはすべて1とする$|e|=1$。

$\textstyle C_i=\frac{2}{deg(i)(deg(i)-1)} \sum_{j,k \in neighbor(i)} |e_{jk}|$

グラフ全体のクラスター係数はその平均値になる。

$\textstyle C =\frac{1}{n} \sum^{n}_{i=1}C_i$

平均頂点間距離

平均頂点間距離はその字のごとく全頂点間の最短路の平均値にあたる。ここでは頂点$i, j$間の最短経路を$p_{ij}$と書く。距離$L$以内にある頂点の数を数えることで求められる。

$\textstyle L=\frac{1}{n} \sum_{i,j\in G}|p_{ij}|$

様々なグラフ

完全グラフ

全ての頂点間に辺を持つグラフは$C=L=1$。

格子

平面の場合は三角格子、正方格子が考えられる。特に、$d$次元空間において辺の長さが単位距離の格子をZ^dと書く。

例. Z²において、$deg(i)=2d$

クラスター係数は定義のままだと0になって面白くないので、最短距離が$a$以下の点には全て辺を持つZ'^dを考えよう。

例. Z'^dのクラスター係数は$\textstyle C=\frac{3(a-1)}{2(2a-1)}$、平均頂点間距離は$\textstyle L=\sqrt[d]{n}/a$

木

全頂点が同じ次数を持つ木を考える。中心の頂点$v_0$を根(root)と呼ぶ。木は定義からサイクルを持たないので$C=0$。平均頂点間距離は

$n = 1 + d + d(d-1) + ... + d(d-1)^L = 1 +d (1-(d-1)^{L+1})/(1-(d-1))$∝$(d-1)^{L+1}$

を用いて

$\textstyle L=\propto \frac{\log n}{\log (d-1)} \propto \log n$

Erdős–Rényiグラフ

各頂点間(全部で$n(n-1)/2$箇所)に一定の確率$p$で独立に辺を作成したランダムグラフをErdős–Rényiグラフと呼ぶ。各頂点に注目してみると$n-1$点に対して確率$p$で辺を張るため、次数は二項分布${}_{n-1}\mbox{C}_k p^k(1-p)^{n-1-k}$に従う。すなわち次数の平均は$c = (n-1)p$と書ける。

ネットワークの進化

次数の平均値$c$に基づくグラフ形状の変化を検証しよう。

$\textstyle c < \frac{1}{n}$

辺の生成される確率が$pn(n-1)/2 \rarr 0$になるため、辺を持たない。

$\textstyle c = 1/\sqrt{n}$

木が生成され始める。

$\textstyle c = const.$

閉路を持つ。ただし、$c$を定数とおいたことで二項分布をポアソン近似した場合、次数は$\textstyle \frac{e^{-c}c^k}{k!}$に従う。平均値はもちろん$c$。

$\textstyle c = \log n$

連結になる。ある頂点が辺を全く持たない確率は$\textstyle (1-p)^{n-1}=((1-\frac{c}{n-1})^{\frac{n-1}{c}})^{c} \leq e^{-c}$。したがって、そのような頂点がグラフ中に存在しない確率の上限は$ne^{-c}$となり、これを0に収束させるには例えば$c \geq 2 \log n$。

この結果は、Erdős–Rényiグラフが連結であるためには次数が$O(\log n)$以上であることを意味し、現実のネットワークのモデルとしてはあまり適切でないことがわかる。

クラスター係数

辺が張られる確率は全て独立なので$C=p \simeq c /n$。