Aritalab:Lecture/NetworkBiology/Erdos-Renyi Model

Wiki Top

Up one level

レポートの書き方

Arita Laboratory

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

歴史と参考図書

• Erdős P, Rényi A. "On Random Graphs. I.". Publicationes Mathematicae 6:290–297, 1959
• Erdős P, Rényi A. "The Evolution of Random Graphs". Publ. Math. Inst. Hung. Acad. Sci 5:17–61, 1960
• Bollobás B. Random Graphs (2nd ed.), Cambridge University Press, 2001
• Durrett R. Random Graph Dynamics, Cambridge University Press, 2004

ネットワークの指標:$C$と$L$

ネットワーク全体についての尺度として、クラスター係数$C$と平均頂点間距離$L$を紹介する。

クラスター係数

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

$\textstyle C_i=\frac{2}{deg(i)(deg(i)-1)} \sum_{j,k \in adj(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$

完全グラフ

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

格子

格子状のネットワークでは頂点が一定間隔で配置されるため、道路網のような地理的制約をうけるつながりを表現するのに適しています。 平面の場合は三角格子、正方格子、六方格子などが考えられます。

ここでは、d 次元空間において辺の長さが単位距離の格子を Z^d と書きましょう。

Z^d において $deg(i) = 2d$

クラスター係数を定義のまま適用すると、正方格子や六方格子は隣接頂点どうしがつながらないために常に0になります。これでは面白くないので、最短距離が $a$ 以下の点には全て辺を張るバリエーションを考えてみましょう。

木

簡単のため全頂点が同じ次数を持つ木を考える。中心の頂点$v_0$を根(root)と呼ぶ。木はその定義よりサイクルを持たないので$C=0$。また平均頂点間距離は、距離L以内にある頂点を数えることで求められる。

$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グラフ

全ての頂点間に一定の確率$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 \le \frac{1}{n^2}$

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

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

辺があったとしても木にしかならない。

$\textstyle c = const.$

各頂点が定数本の辺を持ちはじめる。

• ちょうど$c=1$だと二部グラフのマッチング、$c=2$だと閉路の集合になる。
• 各頂点が持つ辺の本数（の期待値）が$c$なので、$c < 1$のとき連結部分の大きさは高々$\log n$程度にしかならない。しかし$c > 1$の場合繋がっていく確率のほうが高く、その半径(diameter)を$k$とおくと$c^k=n$まで成長できる。このとき$k=\log n / \log c$。
• 詳細な解析によると、臨界点にあたる$c = 1$では連結部分のサイズが$O(n^{2/3})$になることが知られている。

$\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$で十分である。このとき孤立点が消滅する。

辺の数を固定するモデル

辺の数を正確に$N$本とする場合を考えよう。$n$頂点からランダムに2つを選び、その間に辺を作成するプロセスを正確に$N$回繰り返す。(ランダムに頂点を選ぶ回数は$m = 2N$。)これは次数の期待値が$p=2N/n(n-1)$のERグラフにおいて、ちょうど辺数が$N$となった場合に相当する。

ネットワークの特徴

クラスター係数

辺が張られる確率は全て独立なので$C(p)=p \simeq c /n$。これは$K_3$や$K_4$をあまり含まないことを意味している。

平均頂点間距離

各頂点が持つ辺の期待値を$c = (n-1)p$として$L(p) \geq \log n / \log c = O(\log n)$。

連結性

Erdős–Rényiグラフ全体が連結であるためには次数が$O(\log n)$以上必要。