Aritalab:Lecture/NetworkBiology/Percolation

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m (一次元の場合)
m (パーコレーションとは)
 
(6 intermediate revisions by one user not shown)
Line 3: Line 3:
 
==パーコレーションとは==
 
==パーコレーションとは==
  
パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率''p''で占有されるときに生成されるクラスターを解析します。
+
パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率 p で占有されるときに生成されるクラスターを解析します。
様々な格子において、確率 ''p'' がある閾値 <math>p_c</math> に達すると、無限に大きなクラスターが存在し始めます。これを臨界現象といい、臨界点を浸透閾値 (percolation threshold) と呼びます。ある格子点が無限大のクラスターに含まれる確率を浸透確率 (
+
様々な格子において、確率 p がある閾値 p<sub>c</sub> に達すると、無限に大きなクラスターが存在し始めます。これを臨界現象といい、臨界点を浸透閾値 (percolation threshold) と呼びます。ある格子点が無限大のクラスターに含まれる確率を浸透確率 (percolation probability) とよびます。浸透閾値 p<sub>c</sub> はほとんどの場合について厳密解が求まっていませんが、数値シミュレーション等で解析されています。
  
浸透閾値 <math>p_c</math> はほとんどの場合について厳密解が求まっていませんが、数値シミュレーション等で解析されています。
+
上記のように格子点が確率 p で占有される過程を、正確にはサイト過程と呼びます。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率 p で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼びます。
 
+
上記のように格子点が確率 ''p'' で占有される過程を、正確にはサイト過程と呼びます。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率 ''p'' で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼びます。
+
  
 
{| class="wikitable" style="float:right"
 
{| class="wikitable" style="float:right"
 
|-
 
|-
!colspan=3| 主な浸透閾値<math>p_c</math> (*のみ厳密解。<br/>ほとんどの場合解析的に解けない。)
+
!colspan=4| 格子の主な浸透閾値 p<sub>c</sub> (*のみ厳密解。<br/>ほとんどの場合解析的に解けない。)
 
|-
 
|-
! 格子の種類 || サイト || ボンド
+
! 格子の種類 || 配位数 || サイト || ボンド
 
|-
 
|-
| 蜂の巣 || 0.697043 || 0.65271<sup>*</sup>
+
| 蜂の巣 || 3 || 0.697043 || 0.65271<sup>*</sup>
 
|-
 
|-
| 正方 || 0.5927462 || 1/2 <sup>*</sup>
+
| 正方 || 4 || 0.5927462 || 1/2 <sup>*</sup>
 
|-
 
|-
| 三角 || 1/2 <sup>*</sup> || 0.34729<sup>*</sup>
+
| 三角 || 6 || 1/2 <sup>*</sup> || 0.34729<sup>*</sup>
 
|-
 
|-
| ダイヤモンド || 0.4301 || 0.3893
+
| ダイヤモンド || 4 || 0.4301 || 0.3893
 
|-
 
|-
| 単純立方 || 0.311608 || 0.248813
+
| 単純立方 || 6 || 0.311608 || 0.248813
 
|-
 
|-
| 体心立方 || 0.245691 || 0.180287
+
| 体心立方 || 8 || 0.245691 || 0.180287
 
|-
 
|-
| 面心立方<ref>同半径の球を敷き詰めたときの最密充填</ref> || 0.199236 || 0.120163  
+
| 面心立方<ref>同半径の球を敷き詰めたときの最密充填</ref> || 12 || 0.199236 || 0.120163  
 +
|}
 +
<!---
 
|-
 
|-
| d=4 超立方 || 0.196885 || 0.160131
+
| d=4 超立方 || || 0.196885 || 0.160131
 
|-
 
|-
| d=5 超立方 || 0.140797 || 0.118172
+
| d=5 超立方 || || 0.140797 || 0.118172
 
|-
 
|-
| d=6 超立方 || 0.109018 || 0.094202
+
| d=6 超立方 || || 0.109018 || 0.094202
 
|-
 
|-
| d=7 超立方 || 0.088951 || 0.078675
+
| d=7 超立方 || || 0.088951 || 0.078675
|}
+
--->
  
 
==クラスター・周縁という概念==
 
==クラスター・周縁という概念==
Line 51: Line 51:
  
 
無限に長い直線上に一定間隔で格子点がある場合を考えます。
 
無限に長い直線上に一定間隔で格子点がある場合を考えます。
無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないので、浸透閾値 <math>p_c=1</math>、周縁サイズは常に <math>t=2</math> です。この簡便さから、多くの問いに対して厳密解を求められます。
+
無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないので、浸透閾値 p<sub>c</sub> = 1、周縁サイズは常に t = 2 です。この簡便さから、多くの問いに対して厳密解を求められます。
  
  
* ある格子点が、''s''-クラスターに含まれる確率
+
* ある格子点が、s-クラスターに含まれる確率
 
ある格子点は、大きさ s のクラスターのどの位置にもなりうるので s 通りの可能性があります。
 
ある格子点は、大きさ s のクラスターのどの位置にもなりうるので s 通りの可能性があります。
 
:<math>\textstyle P_s = s p_{s,t} = s p^s (1-p)^2</math>
 
:<math>\textstyle P_s = s p_{s,t} = s p^s (1-p)^2</math>
 
* 浸透確率(格子点が無限大のクラスターに含まれる確率)、クラスターの平均サイズ
 
* 浸透確率(格子点が無限大のクラスターに含まれる確率)、クラスターの平均サイズ
 
 
{| class="wikitable"
 
{| class="wikitable"
 
|valign="top"|
 
|valign="top"|
 
|
 
|
;<math>p < p_c = 1</math> の場合  
+
; p < p<sub>c</sub> = 1 の場合  
 
|
 
|
;<math>p = p_c = 1</math> の場合
+
; p = p<sub>c</sub> = 1 の場合
 
|-
 
|-
 
|valign="top"|
 
|valign="top"|
Line 81: Line 80:
 
|}
 
|}
  
平均サイズの計算は説明が必要でしょう。それぞれの s-クラスターが出現する確率にサイズ s をかけたものを、s-クラスターが出現する確率の総和で割れば平均サイズが求まります。
+
平均サイズの計算は説明が必要でしょう。それぞれの s-クラスターが出現する確率 P<sub>s</sub> にサイズ s をかけたものを、s-クラスターが出現する確率の総和で割れば平均サイズが求まります。
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
Line 109: Line 108:
  
 
;特徴
 
;特徴
次数が ''d'' の木の場合、原点は ''d'' 本の枝を持つ。
+
* 次数が d の木の場合、原点は d 本の枝を持つ。
残りの点は通ってきた点のほかに ''d'' &minus; 1 本の枝を持ち、それらの先に確率 ''p'' で占有される格子点が存在する。
+
* 残りの点は通ってきた点のほかに d &minus; 1 本の枝を持ち、それらの先に確率 p で占有される格子点が存在する。
  
先に進める確率は (''d'' &minus; 1) ''p'' になるので、無限大のクラスターが存在し始める値は <math>\textstyle p_c=\frac{1}{d-1}</math>。
+
先に進める確率は (d &minus; 1) p になるので、無限大のクラスターが存在し始める値は p<sub>c</sub> = 1 / (d - 1)、つまり各点に平均 d / (d - 1) 本の枝があれば、無限に大きなクラスターが存在します。
 
+
逆に、これより低い p の値では、無限に大きなクラスターは存在しません。
つまり各点に平均 <math>\textstyle \frac{d}{d-1}</math> 本の枝があれば、無限に大きなクラスターが存在します。
+
逆に、これより低い ''p'' の値では、無限に大きなクラスターは存在しません。
+
 
以降、簡単のため d = 3 ( p<sub>c</sub> = 1/2 ) に話を限定します。
 
以降、簡単のため d = 3 ( p<sub>c</sub> = 1/2 ) に話を限定します。
  
===''d'' = 3 の木===
+
=== d = 3 の木===
ここまでの議論から、浸透閾値は 1/2 である。確率が 1/2 を超えると、その頂点にたどり着いた枝を除いた残り 2 本のうちどちらかがつながっているから、無限大のクラスターが存在する。
+
ここまでの議論から、浸透閾値は 1/2 であり、浸透確率が 1/2 を超えると、その頂点にたどり着いた枝を除いた残り 2 本のうちどちらかがつながっているから、無限大のクラスターが存在します。
  
===浸透確率 ''P''<sub>∞</sub>===
+
===格子点が無限大のクラスターに含まれる確率 P<sub>∞</sub>===
ある格子点が、無限大のクラスターに含まれる確率 (=浸透確率)を求めてみます。
+
p > p<sub>c</sub> = 1 / 2 のとき(無限に大きいクラスターがあるとき)、任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率を Q と書きます。
p > p<sub>c</sub> = 1 / 2 のとき(無限に大きいクラスターがあるとき)、任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率を ''Q'' とします。
+
 
ある近接した格子点から外に無限遠へつながらない確率は、その格子点が占有されていないか、占有されてもその先でつながらない確率を足したもの。
 
ある近接した格子点から外に無限遠へつながらない確率は、その格子点が占有されていないか、占有されてもその先でつながらない確率を足したもの。
これは ''Q'' に等しいはずなので
+
これは Q に等しいはずなので
  
<math>Q = (1-p) + pQ^2</math>
+
:Q = (1 - p) + p Q<sup>2</sup>
  
を満たします。これを解くと<math>Q = 1,\ (1-p)/p</math>。
+
を満たします。これを解くと Q = 1, (1 - p) / p。
  
* <math>Q=1</math>の場合
+
* Q = 1 の場合
無限遠に決してつながらず、<math>p < 1/2</math> のときの <math>P=0</math> に対応します。
+
無限遠に決してつながらず、p < 1/2 のときに対応します。
* <math>Q = (1-p)/p \,</math>の場合
+
* Q = (1 - p) / p の場合
<math>p > 1/2</math> にあたります。
+
p > 1/2 に相当します。 原点が占有されていても無限遠につながらない確率は
原点が占有されていても無限遠につながらない確率は <math>p-P_{\infty} = pQ^3</math>
+
: p  -P<sub></sub> = p Q<sup>3</sup>
これより<math>P_{\infty} = p(1-Q^3) = p - (1-p)^3/p^2</math>
+
 
 +
これより P<sub>∞</sub> = p (1-Q<sup>3</sup>) = p - (1-p)<sup>3</sup> / p<sup>2</sup> です。
  
 
まとめると
 
まとめると
 
{| class ="wikitable" style="text-align:center"
 
{| class ="wikitable" style="text-align:center"
! || <math>p < 1/2</math> || <math>p > 1/2</math>
+
! || <math>\textstyle p < \frac{1}{2}</math> || <math>\textstyle p > \frac{1}{2}</math>
 
|-
 
|-
| 有限のクラスターに含まれる確率 ''F'' || ''p'' || <math>(1-p)^3/p^2</math>
+
| 有限のクラスターに含まれる確率 || p || <math>\textstyle \frac{(1-p)^3}{p^2}</math>
 
|-
 
|-
| 浸透確率 ''P''<sub>∞</sub> = ''p'' &minus; ''F'' || 0 || <math>p - (1-p)^3/p^2</math>
+
| 無限大のクラスターに含まれる確率  || 0 || <math>\textstyle p - \frac{(1-p)^3}{p^2}</math>
 
|}
 
|}
  
===クラスターの平均サイズ ''S''===
+
===クラスターの平均サイズ S===
ある枝の先につながっている格子点数の期待値を <math>T</math> とします。
+
ある枝の先につながっている格子点数の期待値を T とします。
まず <math>p < p_c = 1/2</math> の場合を考えます。
+
まず p < p<sub>c</sub> = 1/2 の場合を考えます。
どの格子点もサイズが無限大のクラスターには属しません。(平均サイズが計算できなくなる。)
+
どの格子点もサイズが無限大のクラスターには属しません。(そうしないと平均サイズが計算できない。)
従って、枝の先にある格子点が占有されていればその格子点プラス二つの枝の平均サイズが付け加わるから
+
枝の先にある格子点が占有されていれば、その格子点プラス二つの枝の平均サイズが付け加わるので
  
<math>T = (1-p)0 +p(1+2T)</math>。 これを解いて<math>T=p/(1-2p)</math>。
+
: T = (1 - p) 0 + p (1 + 2T)
  
 +
これを解いて T = p / (1 - 2p) です。従って、ある頂点が属するクラスターの平均サイズは
  
従って、ある頂点が属するクラスターの平均サイズは
+
: S = 1 + 3T = (1 + p) / (1 - 2p)
 
+
<math>S = 1 + 3T = (1+p)/(1-2p)</math>。
+
 
+
 
+
この議論は容易に一般化できる。次数 ''d'' の場合 <math>p < p_c = 1/(d-1)</math> なら <math>S = (1+p)/(1-dp)</math>。
+
  
 
まとめると
 
まとめると
Line 169: Line 162:
 
| 平均サイズ || <math>\frac{(1+p)}{(1-2p)}</math> || <math>\infty</math>
 
| 平均サイズ || <math>\frac{(1+p)}{(1-2p)}</math> || <math>\infty</math>
 
|}
 
|}
 +
 +
この議論は容易に一般化できます。次数 d の場合 p < p<sub>c</sub> = 1 / (d - 1) なら S = (1 + p) / (1 - dp) です。
 +
 +
  
 
;参考
 
;参考
 
<references/>
 
<references/>

Latest revision as of 14:49, 3 August 2016

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

Contents

[edit] パーコレーションとは

パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率 p で占有されるときに生成されるクラスターを解析します。 様々な格子において、確率 p がある閾値 pc に達すると、無限に大きなクラスターが存在し始めます。これを臨界現象といい、臨界点を浸透閾値 (percolation threshold) と呼びます。ある格子点が無限大のクラスターに含まれる確率を浸透確率 (percolation probability) とよびます。浸透閾値 pc はほとんどの場合について厳密解が求まっていませんが、数値シミュレーション等で解析されています。

上記のように格子点が確率 p で占有される過程を、正確にはサイト過程と呼びます。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率 p で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼びます。

格子の主な浸透閾値 pc (*のみ厳密解。
ほとんどの場合解析的に解けない。)
格子の種類 配位数 サイト ボンド
蜂の巣 3 0.697043 0.65271*
正方  4 0.5927462 1/2 *
三角 6 1/2 * 0.34729*
ダイヤモンド 4 0.4301 0.3893
単純立方 6 0.311608 0.248813
体心立方 8 0.245691 0.180287
面心立方[1] 12 0.199236 0.120163

[edit] クラスター・周縁という概念

各格子点が確率 p で占有されるとし、占有された格子点の集まりをクラスターと呼びます。特に、大きさが s のクラスターを s-クラスターと呼びます。クラスターの周囲の格子点は空でなくてはなりません。クラスターに隣接する空の格子点群を周縁 (perimeter) と呼びます。クラスターが大きくなると内部にも周縁が存在しうるので、周縁と周囲は異なることに注意します。

ある格子点を含む、大きさ s 、周縁 t の異なるクラスターの数を a_{s,t} であらわします。2次元格子の場合は以下のようになります。占有点を黒、非占有点を白、注目している格子点を灰色であらわしています。

a_{1,4} = 1 \quad a_{2,6} = 4 \quad a_{3,8} = 6 \quad a_{3,7} = 12

Lecture-NetworkBiology-Percolation.png

[edit] 一次元の場合

無限に長い直線上に一定間隔で格子点がある場合を考えます。 無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないので、浸透閾値 pc = 1、周縁サイズは常に t = 2 です。この簡便さから、多くの問いに対して厳密解を求められます。


  • ある格子点が、s-クラスターに含まれる確率

ある格子点は、大きさ s のクラスターのどの位置にもなりうるので s 通りの可能性があります。

\textstyle P_s = s p_{s,t} = s p^s (1-p)^2
  • 浸透確率(格子点が無限大のクラスターに含まれる確率)、クラスターの平均サイズ
p < pc = 1 の場合
p = pc = 1 の場合

浸透確率

0
1

平均サイズ

( 1 + p ) / ( 1 - p )
0

平均サイズの計算は説明が必要でしょう。それぞれの s-クラスターが出現する確率 Ps にサイズ s をかけたものを、s-クラスターが出現する確率の総和で割れば平均サイズが求まります。 
\begin{align}
S &= \frac{\sum_s s P_s}{\sum_s P_s}
\end{align}
分母は各点がクラスターに含まれる確率に等しいので p になります。面倒なのは分子の計算です。


\begin{align}
\sum_s s P_s &= (1-p)^2 \sum_s s^2 p^s \\
&= (1-p)^2 \big(p \frac{d}{dp} \big)^2 \sum_s p^s\\
&= (1-p)^2 \big(p \frac{d}{dp} \big) \big(p \frac{d}{dp} \big) \frac{p}{1-p}\\
&= (1-p)^2 \big(p \frac{d}{dp} \big) \frac{p}{(1-p)^2}\\
&= (1-p)^2 p \frac{(1-p)^2 + 2p(1-p)}{(1-p)^4} \\
&= p \frac{1+p}{1-p}
\end{align}

お疲れ様でした。

[edit] 木またはベーテ格子の場合

次数が一定で無限に大きな木をベーテ格子と呼びます(有限の場合はケーリー木とも呼びます。 磁性を扱う方法の一つであるベーテ近似によりこの木の厳密解が求まるため、ベーテ格子と呼ぶようになりました。) ベーテ格子はサイクルを持たない一次元の場合は、次数が2のベーテ格子です。

特徴
  • 次数が d の木の場合、原点は d 本の枝を持つ。
  • 残りの点は通ってきた点のほかに d − 1 本の枝を持ち、それらの先に確率 p で占有される格子点が存在する。

先に進める確率は (d − 1) p になるので、無限大のクラスターが存在し始める値は pc = 1 / (d - 1)、つまり各点に平均 d / (d - 1) 本の枝があれば、無限に大きなクラスターが存在します。 逆に、これより低い p の値では、無限に大きなクラスターは存在しません。 以降、簡単のため d = 3 ( pc = 1/2 ) に話を限定します。

[edit] d = 3 の木

ここまでの議論から、浸透閾値は 1/2 であり、浸透確率が 1/2 を超えると、その頂点にたどり着いた枝を除いた残り 2 本のうちどちらかがつながっているから、無限大のクラスターが存在します。

[edit] 格子点が無限大のクラスターに含まれる確率 P

p > pc = 1 / 2 のとき(無限に大きいクラスターがあるとき)、任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率を Q と書きます。 ある近接した格子点から外に無限遠へつながらない確率は、その格子点が占有されていないか、占有されてもその先でつながらない確率を足したもの。 これは Q に等しいはずなので

Q = (1 - p) + p Q2

を満たします。これを解くと Q = 1, (1 - p) / p。

  • Q = 1 の場合

無限遠に決してつながらず、p < 1/2 のときに対応します。

  • Q = (1 - p) / p の場合

p > 1/2 に相当します。 原点が占有されていても無限遠につながらない確率は

p -P = p Q3

これより P = p (1-Q3) = p - (1-p)3 / p2 です。

まとめると

\textstyle p < \frac{1}{2} \textstyle p > \frac{1}{2}
有限のクラスターに含まれる確率 p \textstyle \frac{(1-p)^3}{p^2}
無限大のクラスターに含まれる確率 0 \textstyle p - \frac{(1-p)^3}{p^2}

[edit] クラスターの平均サイズ S

ある枝の先につながっている格子点数の期待値を T とします。 まず p < pc = 1/2 の場合を考えます。 どの格子点もサイズが無限大のクラスターには属しません。(そうしないと平均サイズが計算できない。) 枝の先にある格子点が占有されていれば、その格子点プラス二つの枝の平均サイズが付け加わるので

T = (1 - p) 0 + p (1 + 2T)

これを解いて T = p / (1 - 2p) です。従って、ある頂点が属するクラスターの平均サイズは

S = 1 + 3T = (1 + p) / (1 - 2p)

まとめると

p < 1/2 p >= 1/2
平均サイズ \frac{(1+p)}{(1-2p)} \infty

この議論は容易に一般化できます。次数 d の場合 p < pc = 1 / (d - 1) なら S = (1 + p) / (1 - dp) です。


参考
  1. 同半径の球を敷き詰めたときの最密充填
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox