Aritalab:Lecture/NetworkBiology/Erdos-Renyi Model
From Metabolomics.JP
ここでは頂点がすべて連結した無向グラフを扱う。
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グラフと呼ぶ。各頂点に注目してみると点に対して確率で辺を張るため、次数は二項分布に従う。すなわち次数の平均は。しかし現実のネットワークは規模に応じて次数が増加するケースが少ないため、一定とおく。このとき二項分布をポアソン近似できて次数の平均はとなる。
クラスター係数
辺が張られる確率は全て独立なので。