Aritalab:Lecture/NetworkBiology/Watts-Strogatz Model - Revision history

Adm at 00:03, 2 August 2017

2017-08-02T00:03:13Z

Adm: /* p = 1 のとき */

2016-08-04T05:53:51Z

‎p = 1 のとき

Adm at 03:10, 3 August 2016

2016-08-03T03:10:14Z

Adm: /* p = 1 のとき */

2014-07-28T00:56:57Z

‎p = 1 のとき

Adm: /* p = 1 のとき */

2011-06-29T23:46:29Z

‎p = 1 のとき

Adm: /* 次数相関 */

2011-06-29T23:45:29Z

‎次数相関

Adm at 22:40, 29 June 2011

2011-06-29T22:40:12Z

Adm: /* 一般の場合 */

2011-06-29T00:01:00Z

‎一般の場合

Adm: /* p = 0 のとき */

2011-06-29T00:00:07Z

‎p = 0 のとき

Adm at 22:23, 28 June 2011

2011-06-28T22:23:25Z

@@ Line 1: / Line 1: @@
-{{Lecture/Header}}
+__TOC__
-−
-{| style="float:right"
-| __TOC__
-|}
 ==スモールワールド==

@@ Line 39: / Line 39: @@
 ;平均頂点間距離
-ある頂点に隣接する頂点数の期待値は <math>\langle k \rangle</math> 個です。隣接点にさらに隣接する頂点数の期待値を求めましょう。
+平均頂点間距離を ''l'' とおき、ある頂点から ''l'' ステップで到達しうる点の数を数えます。ネットワークのサイクルを考慮しないで（大雑把に）''l'' ステップで全点 ''n'' に到達するとしましょう。
-−
-<math>\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} </math>
-−
-を引いているのは、辿ってきた辺を除外するからです。また <math>P(j|k) = P(j)</math> とした部分に次数相関が 0 であることを使っています。この値はポアソン分布なら <math> \langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle </math> であることから <math>\langle k \rangle</math> になります。つまり、何個頂点をたどっても、その先に隣接する頂点の期待値は <math>\langle k \rangle</math> です。
-−
-ここで、平均頂点間距離を ''l'' とおき、ある頂点から ''l'' ステップで到達しうる点の数を数えます。ネットワークのサイクルを考慮しないで（大雑把に）''l'' ステップで全点 ''n'' に到達するとしましょう。
 <math> 1 + \sum^l_{i=1} k^i = \frac{k^{l-1} - 1}{k-1} = n </math>

@@ Line 1: / Line 1: @@
 {{Lecture/Header}}
 ==スモールワールド==
@@ Line 10: / Line 14: @@
 * 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==

@@ Line 48: / Line 48: @@
 === p = 1 のとき===
-全ての辺をランダムに張り替えるので、ランダムグラフになります。<math>kn/2</math> 本の辺がポアソン過程で張られた場合を考えましょう。頂点の平均次数は <math>\langle k \rangle</math> です。また全ての辺はランダムに張られるので、隣り合う頂点の間で次数の相関はありません。
+全ての辺をランダムに張り替えるので、ランダムグラフになります。<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>
 ;クラスター係数

@@ Line 68: / Line 68: @@
 <math> 1 + \sum^l_{i=1} k^i = \frac{k^{l-1} - 1}{k-1} = n </math>
-この関係から、大まかに <math> l \simeq \frac{\log n}{\log k} + \frac{\log (k-1)}{\log k} \simeq \frac{\log n}{\log k}</math> となります。
+この関係から、大まかに <math>L(1) = l \simeq \frac{\log n}{\log k} + \frac{\log (k-1)}{\log k} \simeq \frac{\log n}{\log k}</math> となります。
 ===一般の場合===

@@ Line 16: / Line 16: @@
 生態系のような生物学ネットワークでは負の相関を持つ (disassortative) と考えられます。
-次数相関の存在は次数 ''k'' の頂点につながる頂点の平均次数を調べるとわかります。これを <math> \sum_j j P_{adj}(j|k) </math> と書きましょう。
+次数相関の存在は次数 ''k'' の頂点につながる頂点の平均次数を調べるとわかります。隣接する頂点の次数を <math>P_{adj} ( j | k ) </math> と書きましょう。
 ここで次数 ''k'' と隣接する頂点の次数 ''j'' との相関が0ならば、
@@ Line 29: / Line 29: @@
 で、次数分布や ''k'' によらず一定値となります。
-次数相関 ''r'' をピアソンの相関係数に従って定義しましょう。''M'' 本ある辺の両端点 ''u'', ''v'' の次数をそれぞれ ''k_u'', ''k_v'' とおきます。相関係数の分子は ''k_u'', ''k_v'' の平均からの差分を計算します。
+次数相関 ''r'' をピアソンの相関係数に従って定義しましょう。''M'' 本ある辺の両端点 ''u'', ''v'' の次数をそれぞれ ''k<sub>u</sub>'', ''k<sub>u</sub>'' とおきます。相関係数の分子は ''k<sub>u</sub>'', ''k<sub>v</sub>'' の平均からの差分を計算します。
-分母は ''k_u'' と ''k_v'' の標準偏差の積ですが、実際には分散を計算します。
+分母は ''k<sub>u</sub>'' と ''k<sub>v</sub>'' の標準偏差の積ですが、実際には分散を計算します。
 <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>
 ==Watts-Strogatz Model==

← Older revision		Revision as of 22:40, 29 June 2011
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>
		+

@@ Line 59: / Line 59: @@
 壊れなければよいと考えます。辺が張り替えられる確率はそれぞれ ''p'' ですから 3 つとも張り替えられない確率は
-<math>C(p) = C(0)(1-p)^3\ </math>
+<math>C(p) \simeq C(0)(1-p)^3 \simeq \frac{3}{4}(1-p)^3 </math>
 となります。

@@ Line 19: / Line 19: @@
 ;クラスター係数
-簡単のため左右の隣接点に同じ本数リンクを張ると仮定し、 <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) = 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> です。
 ;平均頂点間距離

@@ Line 15: / Line 15: @@
 各頂点が <math>k</math> 個の隣接点に接続した環状の格子グラフにおいて（総辺数は<math>kn/2</math>）、確率 <math>p</math> で辺を張り直したものをWatts-Strogatzモデルといいます。パラメータ <math>p</math> を調節して格子とランダムグラフの中間状態を作成するところがポイントです。
-=== <math>p=0 \,</math> のとき===
+=== p = 0  のとき===
 ネットワークは環状の格子グラフです。頂点の次数は全て ''k'' です。以下に記すようにクラスター係数が大きい代わりに、平均頂点間距離は O( ''n'' ) になります。
@@ Line 24: / Line 24: @@
 ステップで <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> です。また全ての辺はランダムに張られるので、隣り合う頂点の間で次数の相関はありません。