Aritalab:Lecture/NetworkBiology/Erdos-Renyi Model
m |
m |
||
Line 38: | Line 38: | ||
==ネットワークの進化== | ==ネットワークの進化== | ||
次数の平均値<math>c</math>を変化させて生じるグラフ形状の違いを検証しよう。 | 次数の平均値<math>c</math>を変化させて生じるグラフ形状の違いを検証しよう。 | ||
− | ===<math>\textstyle c \ | + | ===<math>\textstyle c \le \frac{1}{n^2} </math>=== |
辺の生成される確率が<math>pn(n-1)/2 = cn/2 \xrightarrow{n\rarr \infty} 0</math>になるため、辺を持たない。 | 辺の生成される確率が<math>pn(n-1)/2 = cn/2 \xrightarrow{n\rarr \infty} 0</math>になるため、辺を持たない。 | ||
===<math>\textstyle c = 1/\sqrt{n}</math>=== | ===<math>\textstyle c = 1/\sqrt{n}</math>=== | ||
− | + | 辺があったとしても木にしかならない。 | |
+ | |||
===<math>\textstyle c = const.</math>=== | ===<math>\textstyle c = const.</math>=== | ||
− | + | 各頂点が定数本の辺を持ちはじめる。ちょうど1本だけだと二部グラフのマッチング、2本だと閉路の集合になる。各頂点が持つ辺の本数(の期待値)が<math>c</math>なので、<math>c < 1</math>のとき連結しても大きさは高々<math>\log n</math>程度にしかならない。しかし<math>c > 1</math>の場合繋がっていく確率のほうが高く、その半径(diameter)を<math>k</math>とおくと<math>c^k=n</math>まで成長する。このとき<math>k=\log n / \log c</math>。 | |
+ | |||
===<math>\textstyle c = \log n</math>=== | ===<math>\textstyle c = \log n</math>=== | ||
全体が連結になる。ある頂点が辺を全く持たない確率は<math>\textstyle (1-p)^{n-1}=((1-\frac{c}{n-1})^{\frac{n-1}{c}})^{c} \leq e^{-c}</math>。したがって、そのような頂点がグラフ中に存在しない確率の上限は<math>ne^{-c}</math>となり、これを0に収束させるには例えば<math>c \geq 2 \log n</math>で十分である。つまり、孤立点が消滅する。 | 全体が連結になる。ある頂点が辺を全く持たない確率は<math>\textstyle (1-p)^{n-1}=((1-\frac{c}{n-1})^{\frac{n-1}{c}})^{c} \leq e^{-c}</math>。したがって、そのような頂点がグラフ中に存在しない確率の上限は<math>ne^{-c}</math>となり、これを0に収束させるには例えば<math>c \geq 2 \log n</math>で十分である。つまり、孤立点が消滅する。 | ||
− | |||
− | |||
==クラスター係数== | ==クラスター係数== | ||
辺が張られる確率は全て独立なので<math>C=p \simeq c /n</math>。 | 辺が張られる確率は全て独立なので<math>C=p \simeq c /n</math>。 | ||
==平均頂点間距離== | ==平均頂点間距離== | ||
+ | |||
+ | ==その他の特徴== | ||
+ | |||
+ | * Erdős–Rényiグラフ全体が連結であるためには次数が<math>O(\log n)</math>以上必要。 |
Revision as of 10:30, 8 May 2009
ここでは頂点がすべて連結した無向グラフを扱う。
Contents |
歴史
- 1998 Watts DJ, Strogatz S "Collective dynamics of 'small-world' networks". Nature 393: 440–442. doi:10.1038/30918.
ネットワークの指標:と
ネットワーク全体についての尺度として、クラスター係数と平均頂点間距離を紹介する。
クラスター係数
クラスター係数は隣接する頂点間の辺の密度の平均値にあたる。まず各頂点におけるクラスター係数を以下のように定義する。辺の長さはすべて1とする。
グラフ全体のクラスター係数はその平均値になる。
平均頂点間距離
平均頂点間距離はその字のごとく全頂点間の最短路の平均値にあたる。ここでは頂点間の最短経路をと書く。各点に注目する場合は、距離以内にある頂点数を数えることで求められる。
様々なグラフにおけると
完全グラフ
全ての頂点間に辺を持つグラフは。
格子
平面の場合は三角格子、正方格子が考えられる。特に、次元空間において辺の長さが単位距離の格子をZdと書く。
- 例. Z2において、
定義のままだとクラスター係数が0になって面白くないので、最短距離が以下の点には全て辺を張るバリエーションZ'dを考えよう。
- 例. Z'dのクラスター係数は、平均頂点間距離は
木
簡単のため全頂点が同じ次数を持つ木を考える。中心の頂点を根(root)と呼ぶ。木はその定義よりサイクルを持たないので。また平均頂点間距離は、距離L以内にある頂点を数えることで求められる。
- ∝
すなわち
Erdős–Rényiグラフ
全ての頂点間に一定の確率で独立に辺を作成してできるランダムグラフをErdős–Rényiグラフと呼ぶ。各頂点に注目してみると点に対して確率で辺を張るため、次数は二項分布に従う。すなわち次数の平均はと書ける。
ネットワークの進化
次数の平均値を変化させて生じるグラフ形状の違いを検証しよう。
辺の生成される確率がになるため、辺を持たない。
辺があったとしても木にしかならない。
各頂点が定数本の辺を持ちはじめる。ちょうど1本だけだと二部グラフのマッチング、2本だと閉路の集合になる。各頂点が持つ辺の本数(の期待値)がなので、のとき連結しても大きさは高々程度にしかならない。しかしの場合繋がっていく確率のほうが高く、その半径(diameter)をとおくとまで成長する。このとき。
全体が連結になる。ある頂点が辺を全く持たない確率は。したがって、そのような頂点がグラフ中に存在しない確率の上限はとなり、これを0に収束させるには例えばで十分である。つまり、孤立点が消滅する。
クラスター係数
辺が張られる確率は全て独立なので。
平均頂点間距離
その他の特徴
- Erdős–Rényiグラフ全体が連結であるためには次数が以上必要。