Aritalab:Lecture/NetworkBiology/Watts-Strogatz Model

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m (一般の場合)
m
Line 10: Line 10:
 
* Watts DJ, Strogatz SH. "Collective dynamics of 'small-world' networks.". Nature 393 (6684):409–10, 1998. [http://www.ncbi.nlm.nih.gov/sites/entrez?db=pubmed&uid=9623998&cmd=showdetailview&indexed=google doi:10.1038/30918]
 
* Watts DJ, Strogatz SH. "Collective dynamics of 'small-world' networks.". Nature 393 (6684):409–10, 1998. [http://www.ncbi.nlm.nih.gov/sites/entrez?db=pubmed&uid=9623998&cmd=showdetailview&indexed=google doi:10.1038/30918]
 
* Durrett R. "Random Graph Dynamics" Cambridge University Press, 2004.
 
* Durrett R. "Random Graph Dynamics" Cambridge University Press, 2004.
 +
 +
==次数相関==
 +
本題に入る前に、隣接する頂点の次数分布について復習します。隣接する頂点どうしの次数が似る度合いを次数相関といいます。
 +
辺がランダムに張られる場合は次数相関は0になりますが、映画俳優の競演関係といったネットワークはハブどうしが隣接する、つまり正の相関を持つ (assortative) ことが知られています。
 +
生態系のような生物学ネットワークでは負の相関を持つ (disassortative) と考えられます。
 +
 +
次数相関の存在は次数 ''k'' の頂点につながる頂点の平均次数を調べるとわかります。これを <math> \sum_j j P_{adj}(j|k) </math> と書きましょう。
 +
 +
ここで次数 ''k'' と隣接する頂点の次数 ''j'' との相関が0ならば、
 +
次数が ''j'' の頂点は相対的に <math>\frac{j}{\langle k \rangle}</math> だけ、隣にきやすいため
 +
 +
<math> P_{adj}(j|k) = \frac{jp(j)}{\langle k \rangle} </math>
 +
 +
となります。このとき隣接する頂点の平均次数は
 +
 +
<math> \sum_j j P_{adj}(j|k) = \sum_j j \frac{jp(j)}{\langle k \rangle} = \frac{\langle k^2 \rangle}{\langle k \rangle}</math>
 +
 +
で、次数分布や ''k'' によらず一定値となります。
 +
 +
次数相関 ''r'' をピアソンの相関係数に従って定義しましょう。''M'' 本ある辺の両端点 ''u'', ''v'' の次数をそれぞれ ''k_u'', ''k_v'' とおきます。相関係数の分子は ''k_u'', ''k_v'' の平均からの差分を計算します。
 +
分母は ''k_u'' と ''k_v'' の標準偏差の積ですが、実際には分散を計算します。
 +
 +
 +
<math>r = \frac{\sum_{(u,v)\in E}^M (k_u k_v - \langle k \rangle^2) }{M (\langle k^2 \rangle - \langle k \rangle^2) } </math>
 +
  
  

Revision as of 07:40, 30 June 2011

Wiki Top Up one level レポートの書き方 Arita Laboratory

Contents

スモールワールド

ディズニーランドに It's a Small World というアトラクションがあります。友達という概念をネットワークで表現すると、世間の狭さは平均頂点間距離 L が小さいことに相当します。現実のネットワークは平均頂点間距離 L およびクラスター係数 C が大きい ( L = O(log N), C = 0.2 ∼ 0.3 ) ことが特徴です。

ランダムグラフ (Erdos-Renyi Model) は L が小さいものの、C が大きくなりません。 逆に格子グラフは LC も大きくなります。これら二つのグラフの特徴を併せ持つモデルを Watts と Strogatz が提唱して一大ブームになりました。

歴史と参考図書

  • Watts DJ, Strogatz SH. "Collective dynamics of 'small-world' networks.". Nature 393 (6684):409–10, 1998. doi:10.1038/30918
  • Durrett R. "Random Graph Dynamics" Cambridge University Press, 2004.

次数相関

本題に入る前に、隣接する頂点の次数分布について復習します。隣接する頂点どうしの次数が似る度合いを次数相関といいます。 辺がランダムに張られる場合は次数相関は0になりますが、映画俳優の競演関係といったネットワークはハブどうしが隣接する、つまり正の相関を持つ (assortative) ことが知られています。 生態系のような生物学ネットワークでは負の相関を持つ (disassortative) と考えられます。

次数相関の存在は次数 k の頂点につながる頂点の平均次数を調べるとわかります。これを  \sum_j j P_{adj}(j|k) と書きましょう。

ここで次数 k と隣接する頂点の次数 j との相関が0ならば、 次数が j の頂点は相対的に \frac{j}{\langle k \rangle} だけ、隣にきやすいため

 P_{adj}(j|k) = \frac{jp(j)}{\langle k \rangle}

となります。このとき隣接する頂点の平均次数は

 \sum_j j P_{adj}(j|k) = \sum_j j \frac{jp(j)}{\langle k \rangle} = \frac{\langle k^2 \rangle}{\langle k \rangle}

で、次数分布や k によらず一定値となります。

次数相関 r をピアソンの相関係数に従って定義しましょう。M 本ある辺の両端点 u, v の次数をそれぞれ k_u, k_v とおきます。相関係数の分子は k_u, k_v の平均からの差分を計算します。 分母は k_uk_v の標準偏差の積ですが、実際には分散を計算します。


r = \frac{\sum_{(u,v)\in E}^M (k_u k_v - \langle k \rangle^2) }{M (\langle k^2 \rangle - \langle k \rangle^2) }


Watts-Strogatz Model

各頂点が k 個の隣接点に接続した環状の格子グラフにおいて(総辺数はkn/2)、確率 p で辺を張り直したものをWatts-Strogatzモデルといいます。パラメータ p を調節して格子とランダムグラフの中間状態を作成するところがポイントです。

p = 0 のとき

ネットワークは環状の格子グラフです。頂点の次数は全て k です。以下に記すようにクラスター係数が大きい代わりに、平均頂点間距離は O( n ) になります。

クラスター係数

簡単のため左右の隣接点に同じ本数リンクを張ると仮定し、 k = 2i とします。注目する点を原点とした -i \leq x, y \leq i\ のxy座標系を考えます。辺を張るときの端点をそれぞれ x, y と考えると、座標系の中で 2 i + 1 個の頂点間をむすぶ組み合わせは  y > x の領域に属する  (2i + 1) i 個と考えられます。このうち  y \leq x + i に属する部分にはリンクが張られます。その割合(面積)を考えると \ C(0) \simeq 3/4 です。

平均頂点間距離

1ステップで k/2 点スキップでき、環状格子で一番離れている点は n/2 なので、L(0) \leq n / k となります。

p = 1 のとき

全ての辺をランダムに張り替えるので、ランダムグラフになります。kn/2 本の辺がポアソン過程で張られた場合を考えましょう。頂点の平均次数は \langle k \rangle です。また全ての辺はランダムに張られるので、隣り合う頂点の間で次数の相関はありません。

P(k) = \frac{\langle k \rangle^k}{k!}e^{-\langle k \rangle}


クラスター係数

いかなる2頂点であろうと、その間に辺が存在する確率は k/n なので、C(1) \simeq k/n です。

平均頂点間距離

ある頂点に隣接する頂点数の期待値は \langle k \rangle 個です。隣接点にさらに隣接する頂点数の期待値を求めましょう。

\sum_j j P(j|k) -1 = \sum_j j P(j) -1 = \sum_j j \frac{j p(j)}{\langle k \rangle} -1 = \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}

1 を引いているのは、辿ってきた辺を除外するからです。また P(j|k) = P(j) とした部分に次数相関が 0 であることを使っています。この値はポアソン分布なら  \langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle であることから \langle k \rangle になります。つまり、何個頂点をたどっても、その先に隣接する頂点の期待値は \langle k \rangle です。

ここで、平均頂点間距離を l とおき、ある頂点から l ステップで到達しうる点の数を数えます。ネットワークのサイクルを考慮しないで(大雑把に)l ステップで全点 n に到達するとしましょう。

 1 + \sum^l_{i=1} k^i = \frac{k^{l-1} - 1}{k-1} = n

この関係から、大まかに  l \simeq \frac{\log n}{\log k} + \frac{\log (k-1)}{\log k} \simeq \frac{\log n}{\log k} となります。

一般の場合

辺を張りなおすモデルだと理論的解析が難しいので、環状の格子グラフにポアソン過程に従って pkn/2 本の辺を追加するモデルもよく使われます。

平均頂点間距離

導出は面倒ですが以下の近似が知られています。

L(p) = \frac{n}{k}\frac{\log(2 pkn)}{4 pkn}

クラスター係数

簡単な近似では、格子グラフにおいて隣接する頂点どうしが接続した三角形が K_3 が辺の張り直しによって 壊れなければよいと考えます。辺が張り替えられる確率はそれぞれ p ですから 3 つとも張り替えられない確率は

C(p) \simeq C(0)(1-p)^3 \simeq \frac{3}{4}(1-p)^3

となります。

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox