Aritalab:Lecture/NetworkBiology/Erdos-Renyi Model
From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
m |
m |
||
Line 33: | Line 33: | ||
=Erdős–Rényiグラフ= | =Erdős–Rényiグラフ= | ||
− | 各頂点間(全部で<math>n(n-1)/2</math>箇所)に一定の確率<math>p</math>で独立に辺を作成したランダムグラフをErdős–Rényiグラフと呼ぶ。各頂点に注目してみると<math>n-1</math>点に対して確率<math>p</math>で辺を張るため、次数は二項分布<math>{}_{n-1}\mbox{C}_k p^k(1-p)^{n-1-k}</math>に従う。すなわち次数の平均は<math>(n-1)p</math> | + | 各頂点間(全部で<math>n(n-1)/2</math>箇所)に一定の確率<math>p</math>で独立に辺を作成したランダムグラフをErdős–Rényiグラフと呼ぶ。各頂点に注目してみると<math>n-1</math>点に対して確率<math>p</math>で辺を張るため、次数は二項分布<math>{}_{n-1}\mbox{C}_k p^k(1-p)^{n-1-k}</math>に従う。すなわち次数の平均は<math>c = (n-1)p</math>と書ける。 |
+ | |||
+ | ==ネットワークの進化== | ||
+ | 次数の平均値<math>c</math>に基づくグラフ形状の変化を検証しよう。 | ||
+ | ;<math>\textstyle c < \frac{1}{n} </math> | ||
+ | :辺の生成される確率が<math>pn(n-1)/2 \rarr 0</math>になるため、辺を持たない。 | ||
+ | ;<math>\textstyle c = 1/\sqrt{n}</math> | ||
+ | :木が生成され始める。 | ||
+ | ;<math>\textstyle c = const.</math> | ||
+ | :閉路を持つ。ただし、<math>c</math>を定数とおいたことで二項分布をポアソン近似した場合、次数は<math>\textstyle \frac{e^{-c}c^k}{k!}</math>に従う。平均値はもちろん<math>c</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>。 | ||
+ | |||
+ | この結果は、Erdős–Rényiグラフが連結であるためには次数が<math>O(\log n)</math>以上であることを意味し、現実のネットワークのモデルとしてはあまり適切でないことがわかる。 | ||
==クラスター係数== | ==クラスター係数== | ||
− | 辺が張られる確率は全て独立なので<math>C=p \simeq | + | 辺が張られる確率は全て独立なので<math>C=p \simeq c /n</math>。 |
==平均頂点間距離== | ==平均頂点間距離== |
Revision as of 02:23, 7 May 2009
ここでは頂点がすべて連結した無向グラフを扱う。
Contents |
歴史
- 1998 D. J. Watts, Steven Strogatz "Collective dynamics of 'small-world' networks". Nature 393: 440–442. doi:10.1038/30918.
クラスター係数と平均頂点間距離
Link Analysisではグラフにおける各頂点の尺度としてcentralityとprestigeを紹介した。ここではネットワーク全体についての尺度としてクラスター係数と平均頂点間距離を紹介する。
クラスター係数
クラスター係数は隣接する頂点間の辺の密度の平均値にあたる。まず各頂点におけるクラスター係数を以下のように定義する。辺の長さはすべて1とする。
グラフ全体のクラスター係数はその平均値になる。
平均頂点間距離
平均頂点間距離はその字のごとく全頂点間の最短路の平均値にあたる。ここでは頂点間の最短経路をと書く。距離以内にある頂点の数を数えることで求められる。
様々なグラフ
完全グラフ
全ての頂点間に辺を持つグラフは。
格子
平面の場合は三角格子、正方格子が考えられる。特に、次元空間において辺の長さが単位距離の格子をZdと書く。
- 例. Z2において、
クラスター係数は定義のままだと0になって面白くないので、最短距離が以下の点には全て辺を持つZ'dを考えよう。
- 例. Z'dのクラスター係数は、平均頂点間距離は
木
全頂点が同じ次数を持つ木を考える。中心の頂点を根(root)と呼ぶ。木は定義からサイクルを持たないので。平均頂点間距離は
- ∝
を用いて
Erdős–Rényiグラフ
各頂点間(全部で箇所)に一定の確率で独立に辺を作成したランダムグラフをErdős–Rényiグラフと呼ぶ。各頂点に注目してみると点に対して確率で辺を張るため、次数は二項分布に従う。すなわち次数の平均はと書ける。
ネットワークの進化
次数の平均値に基づくグラフ形状の変化を検証しよう。
- 辺の生成される確率がになるため、辺を持たない。
- 木が生成され始める。
- 閉路を持つ。ただし、を定数とおいたことで二項分布をポアソン近似した場合、次数はに従う。平均値はもちろん。
- 連結になる。ある頂点が辺を全く持たない確率は。したがって、そのような頂点がグラフ中に存在しない確率の上限はとなり、これを0に収束させるには例えば。
この結果は、Erdős–Rényiグラフが連結であるためには次数が以上であることを意味し、現実のネットワークのモデルとしてはあまり適切でないことがわかる。
クラスター係数
辺が張られる確率は全て独立なので。