Aritalab:Lecture/NetworkBiology/Percolation

Revision as of 08:13, 17 January 2014

パーコレーションとは

パーコレーション（浸透）理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率pで占有されるときに生成されるクラスターを解析します。様々な格子において、確率　p　がある閾値　 $p_c$ 　に達すると、無限に大きなクラスターが存在し始めます。これを臨界現象といい、臨界点を浸透閾値 (percolation threshold) と呼びます。ある格子点が無限大のクラスターに含まれる確率を浸透確率 (

浸透閾値　 $p_c$ 　はほとんどの場合について厳密解が求まっていませんが、数値シミュレーション等で解析されています。

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

主な浸透閾値 $p_c$ (*のみ厳密解。ほとんどの場合解析的に解けない。)
格子の種類	サイト	ボンド
蜂の巣	0.697043	0.65271^*
正方	0.5927462	1/2 ^*
三角	1/2 ^*	0.34729^*
ダイヤモンド	0.4301	0.3893
単純立方	0.311608	0.248813
体心立方	0.245691	0.180287
面心立方^[1]	0.199236	0.120163
d=4 超立方	0.196885	0.160131
d=5 超立方	0.140797	0.118172
d=6 超立方	0.109018	0.094202
d=7 超立方	0.088951	0.078675

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

各格子点が確率 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$

一次元の場合

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

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

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

$\textstyle P_s = s p_{s,t} = s p^s (1-p)^2$

浸透確率（格子点が無限大のクラスターに含まれる確率）、クラスターの平均サイズ

	$p < p_c = 1$ の場合	$p = p_c = 1$ の場合
浸透確率	0	1
平均サイズ	( 1 + p ) / ( 1 - p )	0

平均サイズの計算は説明が必要でしょう。それぞれの s-クラスターが出現する確率にサイズ 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}$

お疲れ様でした。

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

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

特徴

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

先に進める確率は (d − 1) p になるので、無限大のクラスターが存在し始める値は $\textstyle p_c=\frac{1}{d-1}$ 。

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

d = 3 の木

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

浸透確率 P_∞

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

$Q = (1-p) + pQ^2$

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

$Q=1$ の場合

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

$Q = (1-p)/p \,$ の場合

$p > 1/2$ にあたります。原点が占有されていても無限遠につながらない確率は $p-P_{\infty} = pQ^3$ 。これより $P_{\infty} = p(1-Q^3) = p - (1-p)^3/p^2$ 。

まとめると

	$p < 1/2$	$p > 1/2$
有限のクラスターに含まれる確率 F	p	$(1-p)^3/p^2$
浸透確率 P_∞ = p − F	0	$p - (1-p)^3/p^2$

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

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

$T = (1-p)0 +p(1+2T)$ 。これを解いて $T=p/(1-2p)$ 。

従って、ある頂点が属するクラスターの平均サイズは

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

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