Aritalab:Lecture/NetworkBiology/Percolation on Graph - Revision history

Adm at 03:19, 6 August 2016

2016-08-06T03:19:00Z

Adm: /* パーコレーションの起こりやすさ */

2016-08-06T03:10:11Z

‎パーコレーションの起こりやすさ

Adm: /* グラフ上のパーコレーション */

2016-08-03T06:47:53Z

‎グラフ上のパーコレーション

Adm: /* 占有される頂点の母関数 */

2015-08-28T01:35:10Z

‎占有される頂点の母関数

Adm: /* 次数分布の母関数 */

2015-08-28T01:31:06Z

‎次数分布の母関数

Adm: /* 占有される頂点の母関数 */

2014-01-17T01:19:27Z

‎占有される頂点の母関数

Adm: /* 占有される頂点の母関数 */

2014-01-17T00:33:00Z

‎占有される頂点の母関数

Adm: /* 占有される頂点の母関数 */

2013-01-31T04:44:30Z

‎占有される頂点の母関数

Adm: /* スケールフリーネットワークの場合 */

2011-06-24T07:24:12Z

‎スケールフリーネットワークの場合

Adm: /* 占有される頂点の母関数 */

2011-06-16T03:23:02Z

‎占有される頂点の母関数

@@ Line 3: / Line 3: @@
 ==グラフ上のパーコレーション==
-グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。
+グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。ここでの議論は[[Aritalab:Lecture/Basic/GF_DegreeDistribution|母関数を使った説明]]もあります。
-母関数の説明を理解するには、[[Aritalab:Lecture/Basic/Generating Function|母関数の概念]]を復習しておいてください。
-ただ、面倒な説明を使わなくても言っていることは以下のとおりです。あるネットワークの平均次数が <k> で与えられるとき、隣接点の平均次数は (<k<sup>2</sup>> - <k>) / <k> になります。この本数の枝のうち、確率 q でサイトが ON になる場合、隣接点の周りで占有される頂点数は q (<k<sup>2</sup>> - <k>) / <k> になります。これが 1 を上回る場合は臨界になるので、1 = q (<k<sup>2</sup>> - <k>) / <k> を解いて、q<sub>c</sub> = 1 / (<k<sup>2</sup>> / <k>) - 1 が得られます。つまり、<k<sup>2</sup>> / <k> のバランスに臨界確率が左右されるということです。
+あるネットワークの平均次数が <k> で与えられるとき、隣接点の平均次数は <math>\textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}</math> になります。この本数のうち、確率 q でサイトが ON になる場合、隣接点の周りで占有される頂点数は <math>q \textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}</math>  になります。これが 1 を上回る場合に相転移をおこすので、臨界確率 <math>q_c = \textstyle \frac{1}{\langle k^2 \rangle / \langle k \rangle - 1 }</math>  が得られます。つまり、<k<sup>2</sup>> / <k> のバランスに臨界確率が左右されるということです。
-−
-==次数分布の母関数==
-グラフの次数分布 <math>p(k)</math> を与えられたとき、その母関数は
-−
-<math>G_v(x) = \sum p(k) x^k</math>
-−
-になります。しかし、頂点 ''v'' の隣にある頂点 ''w'' の次数分布はもはや <math>p(k)</math> ではありません。
-選ばれた辺の先には、他の点が等確率でくることはないからです。例えば、スケールフリーネットワークの中からランダムに１つ頂点を選ぶと次数の少ないものが選ばれますが、そこから辺を１つたどった先はハブ頂点につながる確率が高くなります。つまり、次数が大きいほうが、（次数に比例して）存在する確率が高くなります。
-−
-辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えましょう。
-もう片側の端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した値になります（分母は正規化定数）。
-−
-<math>\frac{kp(k)}{\sum_j jp(j)}</math>
-−
-よってある頂点 ''v'' の隣にくる頂点 ''w'' の次数分布の母関数は以下のとおりです。
-−
-<math>\sum_{k=0}^{\infty}x^k\frac{kp(k)}{\sum_jjp(j)} = x\frac{\sum_k kx^{(k-1)}p(k)}{\sum_jjp(j)} = x\frac{G'_v(x)}{G'_v(1)}</math>
-−
-母関数においては、次数 <math>k</math> に対して <math>x^k</math> が対応します。
-頂点 ''v'' の先に ''w'' がついているとき、''w'' から ''v'' 以外に伸びる辺数に注目しましょう。
-''v'' から ''w'' への辺1本ぶんを除いた ''w'' に関する母関数は、上の式を<math>x</math>で割ったものにあたります。
-−
-<math>G_w(x) = \frac{G'_v(x)}{G'_v(1)}</math>
-−
-==占有される頂点の母関数==
-−
-パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときです。
-ただし、このときの母関数はグラフ全体の次数分布を示す <math>G_v</math> ではなく、占有された頂点のみによる部分ネットワークの母関数です。
-したがって、母関数を区別して <math>F_v</math> と記しましょう。また ''G'' の平均次数を <math>\langle k \rangle</math> とします。平均次数を母関数を用いて表現すると、占有された頂点のみの平均次数がわかります
-　(式の導出は[[Aritalab:Lecture/Basic/Probability_Generating_Function|確率母関数のページ]]を参照）。
-−
-<math>
-\begin{align}
-F'_v(1) &= q G'_v(1) = q \langle k \rangle
-\end{align}
 </math>
-−
-相転移が起きるのは<math>F_w'(1) = 1</math>のときです。
-−
-<math>
-\begin{align}
-F'_w(1) &= q G'_w(1) = q \Big(\frac{G'_v(x)}{G'_v(1)}\Big)' \Big|_{x=1}
-= q \frac{G''_v(1)}{G'_v(1)}
-\end{align}
-</math>
-−
-<math>G''_v(1) = \langle k^2 \rangle - \langle k \rangle, G'_v(1) = \langle k \rangle</math>を代入すると
 <math>
-q_c = \frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle} - 1}
 </math>
-−
-すなわち、<math>\langle k^2 \rangle</math>が大きく <math>\langle k \rangle</math> を上回るときに　<math>q_c</math> は小さくなります。
-ハブの ''k'' は大きくなりますから、<math>k^2</math> は更に大きくなります。次数の大きなハブがあるほど、パーコレーションが起きやすいということです。また全ての次数が同じとき、 <math>\langle k^2 \rangle = \langle k \rangle^2</math> となりベーテ格子の結果と一致します。
 ==パーコレーションの起こりやすさ==
-いかなる次数分布でも、<math>\langle k^2 \rangle</math>が<math>\langle k \rangle</math>に比して大きいと、低い浸透確率で相転移が起こることをみてきました。
+いかなる次数分布でも、<math>\langle k^2 \rangle</math>が<math>\langle k \rangle</math>に比して大きいと、低い浸透確率で相転移が起こります。
 ===格子グラフ、Erdosブラフ===

@@ Line 65: / Line 65: @@
 いかなる次数分布でも、<math>\langle k^2 \rangle</math>が<math>\langle k \rangle</math>に比して大きいと、低い浸透確率で相転移が起こることをみてきました。
-===ランダムグラフの場合===
+===格子グラフ、Erdosブラフ===
-次数の分布がポアソン分布になるランダムグラフをかんがえましょう。平均と分散は等しく　<math>E[k] = V[k] = \langle k \rangle </math> になります。
+次数分布がポアソン分布をなす場合、平均と分散は等しく　<math>E[k] = V[k] = \langle k \rangle </math> になります。
-このとき<math>\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle </math>になるので
+このとき <math>\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle </math> です。この場合も格子グラフとほぼ同じで、平均次数に反比例して浸透確率が下がります。
-<math>q_c = 1 / \langle k \rangle</math>
+===スケールフリーネットワーク===
-−
-すなわち、平均次数に反比例して浸透確率が下がっていきます。
-−
-===スケールフリーネットワークの場合===
 次数の分布が、べき分布 <math>p(k)=Ck^{-\gamma}</math> のときをかんがえましょう。

@@ Line 4: / Line 4: @@
 グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。
-この内容を読む前に[[Aritalab:Lecture/Basic/Generating Function|母関数の概念]]を復習しておいてください。
+母関数の説明を理解するには、[[Aritalab:Lecture/Basic/Generating Function|母関数の概念]]を復習しておいてください。
 ==次数分布の母関数==

@@ Line 33: / Line 33: @@
 パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときです。
 ただし、このときの母関数はグラフ全体の次数分布を示す <math>G_v</math> ではなく、占有された頂点のみによる部分ネットワークの母関数です。
-したがって、母関数を区別して <math>F_v</math> と記しましょう。関数 ''F'' と ''G'' の関係は、各頂点が確率 ''q'' で占有されるため ''G'' と ''F'' の次数平均をそれぞれ<math>\langle k \rangle</math>, <math>\langle l \rangle</math>
+したがって、母関数を区別して <math>F_v</math> と記しましょう。また ''G'' の平均次数を <math>\langle k \rangle</math> とします。平均次数を母関数を用いて表現すると、占有された頂点のみの平均次数がわかります
-と書くと
+　(式の導出は[[Aritalab:Lecture/Basic/Probability_Generating_Function|確率母関数のページ]]を参照）。
-<math>
-\begin{align}
-\langle l \rangle &= q \langle k \rangle \\
-\end{align}
-</math>
-です。
-−
-この関係から　(式の導出は[[Aritalab:Lecture/Basic/Probability_Generating_Function|確率母関数のページ]]を参照）
 <math>

@@ Line 12: / Line 12: @@
 になります。しかし、頂点 ''v'' の隣にある頂点 ''w'' の次数分布はもはや <math>p(k)</math> ではありません。
-選ばれた辺の先には、他の点が等確率でくることはないからです。
+選ばれた辺の先には、他の点が等確率でくることはないからです。例えば、スケールフリーネットワークの中からランダムに１つ頂点を選ぶと次数の少ないものが選ばれますが、そこから辺を１つたどった先はハブ頂点につながる確率が高くなります。つまり、次数が大きいほうが、（次数に比例して）存在する確率が高くなります。
 辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えましょう。
-次数の大きい点のほうが、次数に比例して存在する確率が高くなります。
+もう片側の端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した値になります（分母は正規化定数）。
-つまり、もう片側にある端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した<math>\textstyle kp(k)/\Sigma_j jp(j)</math>となります（分母は正規化定数）。
-よってある頂点 ''v'' の隣にくる頂点 ''w'' の次数分布の母関数は
+<math>\frac{kp(k)}{\sum_j jp(j)}</math>
-<math>\sum_{k=0}^{\infty}x^k\frac{kp(k)}{\Sigma_jjp(j)} = x\frac{\Sigma_k kx^{(k-1)}p(k)}{\Sigma_jjp(j)} = x\frac{G'_v(x)}{G'_v(1)}</math>
+<math>\sum_{k=0}^{\infty}x^k\frac{kp(k)}{\sum_jjp(j)} = x\frac{\sum_k kx^{(k-1)}p(k)}{\sum_jjp(j)} = x\frac{G'_v(x)}{G'_v(1)}</math>
 母関数においては、次数 <math>k</math> に対して <math>x^k</math> が対応します。

@@ Line 44: / Line 44: @@
 \begin{align}
 F'_v(1) &= q G'_v(1) = q \langle k \rangle \\
-F''_v(1) &= q^2G''_v(1) = q^2 \langle k^2 \rangle - q \langle k \rangle
+F''_v(1) &= q^2G''_v(1) - q G'_v(1) = q^2 \langle k^2 \rangle - q \langle k \rangle
 \end{align}
 </math>

@@ Line 83: / Line 83: @@
 次数の分布が、べき分布 <math>p(k)=Ck^{-\gamma}</math> のときをかんがえましょう。
 <math>
-\frac{\langle k^2 \rangle}{\langle k \rangle} = \frac{\Sigma_kk^2p(k)}{\Sigma_kkp(k)} = \frac{\Sigma k^{2-\gamma}}{ \Sigma k^{1-\gamma}}
+\frac{\langle k^2 \rangle}{\langle k \rangle} = \frac{\Sigma_kk^2p(k)}{\Sigma_kkp(k)} = \frac{\Sigma k^{2-\gamma}}{ \Sigma k^{1-\gamma}} = \frac{\zeta(\gamma - 2)}{\zeta(\gamma - 1)}
 </math>

@@ Line 48: / Line 48: @@
 </math>
-相転移が起きるのは<math>F_w'(1) = 1</math>のとき。
+相転移が起きるのは<math>F_w'(1) = 1</math>のときです。
 <math>