Aritalab:Lecture/NetworkBiology/Watts-Strogatz Model

Latest revision as of 09:03, 2 August 2017

[edit] スモールワールド

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

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

[edit] 歴史と参考図書

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.

[edit] Watts-Strogatz Model

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

[edit] 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$ となります。

[edit] p = 1 のとき

全ての辺をランダムに張り替えるので、ランダムグラフになります。 $kn/2$ 本の辺をポアソン過程で張る場合を考えましょう。頂点の平均次数は $\langle k \rangle$ です。発生回数の期待値がλのポアソン分布は $P(X=k)=\frac{\lambda^{k}}{k!}e^{-\lambda}$ で表されることに注意します。

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

全ての辺はランダムに張られるので、隣り合う頂点の間で次数の相関はありません。

クラスター係数

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

平均頂点間距離

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

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

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

[edit] 一般の場合

辺を張りなおすモデルだと理論的解析が難しいので、環状の格子グラフにポアソン過程に従って $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$

となります。

@@ Line 1: / Line 1: @@
-=歴史と参考図書=
+__TOC__
+==スモールワールド==
+ディズニーランドに It's a Small World というアトラクションがあります。友達という概念をネットワークで表現すると、世間の狭さは平均頂点間距離 ''L'' が小さいことに相当します。現実のネットワークは平均頂点間距離 ''L'' およびクラスター係数 ''C'' が大きい ( ''L'' = O(log ''N''), ''C'' = 0.2 &sim; 0.3 ) ことが特徴です。
+ランダムグラフ (Erdos-Renyi Model) は ''L'' が小さいものの、''C'' が大きくなりません。
+逆に格子グラフは ''L'' も ''C'' も大きくなります。これら二つのグラフの特徴を併せ持つモデルを Watts と Strogatz が提唱して一大ブームになりました。
+==歴史と参考図書==
 * 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.
-=Watts-Strogatz Model=
+==Watts-Strogatz Model==
-各頂点が<math>k</math>個の隣接点に接続した環状の格子グラフにおいて（総辺数は<math>kn/2</math>）、確率<math>p</math>で辺を張り直したものをWatts-Strogatzモデルという。辺を張りなおすモデルは解析が難しいので、環状の格子グラフにポアソン過程として<math>pkn/2</math>本の辺を追加するモデルがよく使われる。パラメータ<math>p</math>を調節して格子とランダムグラフの中間状態を作成する点がポイント。
+各頂点が <math>k</math> 個の隣接点に接続した環状の格子グラフにおいて（総辺数は<math>kn/2</math>）、確率 <math>p</math> で辺を張り直したものをWatts-Strogatzモデルといいます。パラメータ <math>p</math> を調節して格子とランダムグラフの中間状態を作成するところがポイントです。
+=== p = 0  のとき===
+ネットワークは環状の格子グラフです。頂点の次数は全て ''k'' です。以下に記すようにクラスター係数が大きい代わりに、平均頂点間距離は O( ''n'' ) になります。
-==<math>p=0</math>のとき==
 ;クラスター係数
-簡単のため左右の隣接点に同じ本数リンクを張ると仮定し、<math>k = 2i</math>とする。注目する点を原点とした<math>-i \leq x, y < \leq i</math>のxy座標系を考えたとき、<math>|x - y| > i</math>に対応する座標点は三角形<math>K_3</math>を形成せず、残りは形成する。その割合を考えると<math>C(0) = 3/4</math>。
+簡単のため左右の隣接点に同じ本数リンクを張ると仮定し、 <math>k = 2i</math> とします。注目する点を原点とした <math>-i \leq x, y \leq i\ </math> のxy座標系を考えます。辺を張るときの端点をそれぞれ x, y と考えると、座標系の中で 2 ''i'' + 1 個の頂点間をむすぶ組み合わせは <math> y > x </math> の領域に属する <math> (2i + 1) i </math> 個と考えられます。このうち <math> y \leq x + i</math> に属する部分にはリンクが張られます。その割合（面積）を考えると <math>\ C(0) \simeq 3/4</math> です。
 ;平均頂点間距離
-ステップで<math>k/2</math>点スキップでき、環状格子で一番離れている点は<math>n/2</math>なので、<math>L(0) \leq n / k</math>。
+ステップで <math>k/2</math> 点スキップでき、環状格子で一番離れている点は <math>n/2</math> なので、<math>L(0) \leq n / k</math> となります。
-==<math>p=1</math>のとき==
-ランダムグラフと思えばよい。
+=== p = 1 のとき===
+全ての辺をランダムに張り替えるので、ランダムグラフになります。<math>kn/2</math> 本の辺をポアソン過程で張る場合を考えましょう。頂点の平均次数は <math>\langle k \rangle</math> です。発生回数の期待値がλのポアソン分布は<math>P(X=k)=\frac{\lambda^{k}}{k!}e^{-\lambda}</math>で表されることに注意します。
+<math>P(k) = \frac{\langle k \rangle^k}{k!}e^{-\langle k \rangle}</math>
+全ての辺はランダムに張られるので、隣り合う頂点の間で次数の相関はありません。
 ;クラスター係数
-<math>k</math>辺を張りかえるとき、<math>n</math>頂点の中から<math>k</math>隣接点を選べばよいので<math>C(1) \simeq k/n</math>。
+いかなる2頂点であろうと、その間に辺が存在する確率は <math>k/n</math> なので、<math>C(1) \simeq k/n</math> です。
 ;平均頂点間距離
-辺をランダムに張りかえるので<math>L(1) \simeq \log n / \log k</math>。
-==一般の場合==
+平均頂点間距離を ''l'' とおき、ある頂点から ''l'' ステップで到達しうる点の数を数えます。ネットワークのサイクルを考慮しないで（大雑把に）''l'' ステップで全点 ''n'' に到達するとしましょう。
+<math> 1 + \sum^l_{i=1} k^i = \frac{k^{l-1} - 1}{k-1} = n </math>
+この関係から、大まかに <math>L(1) = l \simeq \frac{\log n}{\log k} + \frac{\log (k-1)}{\log k} \simeq \frac{\log n}{\log k}</math> となります。
+===一般の場合===
+辺を張りなおすモデルだと理論的解析が難しいので、環状の格子グラフにポアソン過程に従って <math>pkn/2</math> 本の辺を追加するモデルもよく使われます。
 ;平均頂点間距離
-導出は面倒だが以下の近似が知られている。<math>\textstyle L(p)=\frac{n}{k}\frac{\log(2 pkn)}{4 pkn}</math>
+導出は面倒ですが以下の近似が知られています。
+<math>L(p) = \frac{n}{k}\frac{\log(2 pkn)}{4 pkn}</math>
 ;クラスター係数
-簡単な近似では、<math>K_3</math>をなす3頂点間の辺が張りなおしを防げばよいので
+簡単な近似では、格子グラフにおいて隣接する頂点どうしが接続した三角形が <math>K_3</math> が辺の張り直しによって
-<math>L(p) = L(0)(1-p)^3</math>。
+壊れなければよいと考えます。辺が張り替えられる確率はそれぞれ ''p'' ですから 3 つとも張り替えられない確率は
+<math>C(p) \simeq C(0)(1-p)^3 \simeq \frac{3}{4}(1-p)^3 </math>
+となります。

Aritalab:Lecture/NetworkBiology/Watts-Strogatz Model

Latest revision as of 09:03, 2 August 2017

Contents

[edit] スモールワールド

[edit] 歴史と参考図書

[edit] Watts-Strogatz Model

[edit] p = 0 のとき

[edit] p = 1 のとき

[edit] 一般の場合

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox