Aritalab:Lecture/NetworkBiology/Percolation

Revision as of 09:52, 9 June 2011

パーコレーションとは

パーコレーション（浸透）理論 (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,7} = 12 \quad a_{3,8} = 6$

母関数とよく使う記法

これからよく使う記法を母関数　 $\textstyle A(x,y) = \sum_{s,t} a_{s,t} x^s y^t$ 　を使ってまとめておく。

ある格子点が、大きさs、周縁tのクラスターに含まれる確率

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

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

$\textstyle P_s = \sum_t p_{s,t}$

ある格子点が、有限の大きさのクラスターに含まれる確率

$\textstyle F = \sum_{s,t} p_{s,t} = \sum_s P_s = A(p, 1-p)$

ある格子点が、無限大のクラスターに含まれる確率（=浸透確率）

$\textstyle P_{\infty} = p - F$

ある格子点が含まれる、有限の大きさのクラスターの平均サイズ

$S = \frac{\sum_{s,t} s p_{s,t}}{F} = \frac{\sum_s s P_s}{\sum_s P_s} = x\frac{\partial}{\partial x}\log A(x,y) \Bigg|_{x=p,\ y=1-p}$

個々のクラスターを1回だけ数えたときの、クラスターの平均サイズ

$\langle s \rangle = \frac{\sum_s P_s}{\sum_s (1/s)P_s}$

一次元の場合

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

母関数 $\textstyle A(x,y) = \sum_s s x^s y^2 = \frac{xy^2}{(1-x)^2}$

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

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

ある格子点が、有限の大きさのクラスターに含まれる確率

$\textstyle F = \sum_{s,t} p_{s,t} = \sum_s P_s = p$

ある格子点が、無限大のクラスターに含まれる確率（=浸透確率）

$\textstyle P_{\infty} = p - F = 0$

ある格子点が含まれる、有限の大きさのクラスターの平均サイズ

$\begin{align} S &= \textstyle \frac{\sum_{s,t} s p_{s,t}}{F} = \frac{\sum_s s P_s}{\sum_s P_s} = \frac{x}{p} \frac{\partial}{\partial x} A(x,y) \Big|_{x=p,\ y=1-p}\\ &= \textstyle \frac{(1-p)^4 + 2p(1-p)^2(1-p)}{(1-p)^4} = \frac{1+p}{1-p} \end{align}$

個々のクラスターを1回だけ数えたときの、クラスターの平均サイズ

$\textstyle \langle s \rangle = \frac{\sum_s P_s}{\sum_s (1/s)P_s}$

相関関数と相関距離

ある占有された格子点から $r$ だけ離れた格子点が同じクラスターに属する確率を $g(r)$ であらわし、相関関数とよぶ。

$\textstyle g(r) = p^r = \exp( -r / \xi )$

ここで $\textstyle \xi = -\frac{1}{\log(p)} \sim \frac{1}{1 - p} = \frac{1}{p_c-p}$ 。この　 $\xi$ 　を相関距離という。

大まかにいうと、相関距離はクラスターの差し渡しに比例する。一次元の場合は、 1列に並ぶだけなので　 $\textstyle S \propto \xi (p \rightarrow p_c)$ が成立する。また $\textstyle \Sigma_r g(r) = S$ も成立する。

証明: 一次元の場合、r ステップ離れた箇所まで全ての点が占有されねばならないから $\textstyle g(0) = 1,\ g(1)= p,\ g(2) = p^2, g(r) = p^r$ が成立。; $\textstyle \Sigma_r g(r) = \Sigma_0^{\infty}g(r) + \Sigma_0^{-\infty}g(r) - g(0) = 2 \frac{1-p^{\infty}}{1-p} - 1 = \frac{1+p}{1-p} = S$ 。(証明終)

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

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

次数が d の木の場合、原点は d 本の枝を持つ。残りの点は通ってきた点のほかに $d-1$ 本の枝を持ち、それらの先に確率 p で占有される格子点が存在する。先に進める確率は $(d-1)p$ になるので、無限大のクラスターが存在し始める値は $\textstyle p_c=\frac{1}{d-1}$ 。つまり各点からみて平均 $\textstyle \frac{d}{d-1}$ 本つながっていれば、無限に大きなクラスターになる。逆に、これより低い p の値では、無限に大きなクラスターは存在しない。以降、簡単のため $\textstyle d=3\ (p_c = 1/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$ に対応する。 $p > 1/2$ のとき、 $Q = (1-p)/p$ を考える。原点が占有されていても無限遠につながらない確率は $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_∞	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)$ 。

↑ 同半径の球を敷き詰めたときの最密充填

[0] 同半径の球を敷き詰めたときの最密充填

[1]

@@ Line 125: / Line 125: @@
 ! || <math>p < 1/2</math> || <math>p > 1/2</math>
 |-
-| ''F'' || ''p'' || <math>(1-p)^3/p^2</math>
+| ある点が有限のクラスターに含まれる確率 ''F'' || ''p'' || <math>(1-p)^3/p^2</math>
 |-
-| ''P''<sub>∞</sub> || 0 || <math>p - (1-p)^3/p^2</math>
+| ある点が無限のクラスターに含まれる確率 ''P''<sub>∞</sub> || 0 || <math>p - (1-p)^3/p^2</math>
 |}

Aritalab:Lecture/NetworkBiology/Percolation

Revision as of 09:52, 9 June 2011

Contents

パーコレーションとは

クラスターと周縁

母関数とよく使う記法