Aritalab:Lecture/NetworkBiology/Percolation
m |
|||
Line 4: | Line 4: | ||
パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率''p''で占有されるときに生成されるクラスターを解析する。 | パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率''p''で占有されるときに生成されるクラスターを解析する。 | ||
− | + | 様々な格子において、確率 ''p'' がある閾値 <math>p_c</math> に達すると、無限に大きなクラスターが存在し始める(臨界現象)。この値を浸透閾値 (percolation threshold) と呼ぶ。浸透閾値 <math>p_c</math> はほとんどの場合について厳密解が求まっていないが、数値シミュレーション等で解析されている。 | |
− | 上記のように格子点が確率''p''で占有される過程を、正確にはサイト過程と呼ぶ。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率''p''で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼ぶ。 | + | 上記のように格子点が確率 ''p'' で占有される過程を、正確にはサイト過程と呼ぶ。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率 ''p'' で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼ぶ。 |
{| class="wikitable" style="float:right" | {| class="wikitable" style="float:right" | ||
Line 38: | Line 38: | ||
==クラスターと周縁== | ==クラスターと周縁== | ||
− | 各格子点は確率''p''で占有されるとし、占有された格子点の集まりをクラスターと呼ぶ。特に、大きさが''s''のクラスターを''s-''クラスターと呼ぶ。クラスターの周囲の格子点は空でなくてはならない。クラスターに隣接する空の格子点群を周縁 (perimeter) と呼ぶ。クラスターが大きくなると内部にも周縁が存在しうるので、周縁と周囲は異なることに注意しよう。 | + | 各格子点は確率 ''p'' で占有されるとし、占有された格子点の集まりをクラスターと呼ぶ。特に、大きさが ''s'' のクラスターを ''s-''クラスターと呼ぶ。クラスターの周囲の格子点は空でなくてはならない。クラスターに隣接する空の格子点群を周縁 (perimeter) と呼ぶ。クラスターが大きくなると内部にも周縁が存在しうるので、周縁と周囲は異なることに注意しよう。 |
− | ある格子点を含む、大きさ''s''、周縁''t''の異なるクラスターの数を<math>a_{s,t}</math>であらわす。2次元格子の場合、以下のようになる。 | + | ある格子点を含む、大きさ ''s'' 、周縁 ''t'' の異なるクラスターの数を <math>a_{s,t}</math> であらわす。2次元格子の場合、以下のようになる。 |
<math>a_{1,4} = 1 \quad a_{2,6} = 4 \quad a_{3,7} = 12 \quad a_{3,8} = 6</math> | <math>a_{1,4} = 1 \quad a_{2,6} = 4 \quad a_{3,7} = 12 \quad a_{3,8} = 6</math> | ||
Line 85: | Line 85: | ||
===相関関数と相関距離=== | ===相関関数と相関距離=== | ||
− | ある占有された格子点から<math>r</math>だけ離れた格子点が同じクラスターに属する確率を<math>g(r)</math>であらわし、相関関数とよぶ。 | + | ある占有された格子点から <math>r</math> だけ離れた格子点が同じクラスターに属する確率を <math>g(r)</math> であらわし、相関関数とよぶ。 |
<math>\textstyle g(r) = p^r = \exp( -r / \xi )</math> | <math>\textstyle g(r) = p^r = \exp( -r / \xi )</math> | ||
− | ここで<math>\textstyle \xi = -\frac{1}{\log(p)} \sim \frac{1}{1 - p} = \frac{1}{p_c-p}</math> | + | ここで<math>\textstyle \xi = -\frac{1}{\log(p)} \sim \frac{1}{1 - p} = \frac{1}{p_c-p}</math>。この <math>\xi</math> を相関距離という。 |
− | + | 大まかにいうと、相関距離はクラスターの差し渡しに比例する。一次元の場合は、 1列に並ぶだけなので <math>\textstyle S = \xi (p \rightarrow p_c)</math> が成立する。また <math>\textstyle \Sigma_r g(r) = S</math> も成立する。 | |
;証明 | ;証明 | ||
− | : | + | :一次元の場合、''r'' ステップ離れた箇所まで全ての点が占有されねばならないから <math>\textstyle g(0) = 1,\ g(1)= p,\ g(2) = p^2, g(r) = p^r</math>が成立。 |
:<math>\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</math>。(証明終) | :<math>\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</math>。(証明終) | ||
Line 107: | Line 107: | ||
つまり各点からみて平均 <math>\textstyle \frac{d}{d-1}</math> 本つながっていれば、無限に大きなクラスターになる。 | つまり各点からみて平均 <math>\textstyle \frac{d}{d-1}</math> 本つながっていれば、無限に大きなクラスターになる。 | ||
逆に、これより低い ''p'' の値では、無限に大きなクラスターは存在しない。 | 逆に、これより低い ''p'' の値では、無限に大きなクラスターは存在しない。 | ||
− | 以降、簡単のため <math>d=3\ (p_c = 1/2)</math> に話を限定する。 | + | 以降、簡単のため <math>\textstyle d=3\ (p_c = 1/2)</math> に話を限定する。 |
母関数を求めるのはややこしいが、興味のある人は「パーコレーションの科学」(小田垣 孝著 裳華房)を参照してほしい。 | 母関数を求めるのはややこしいが、興味のある人は「パーコレーションの科学」(小田垣 孝著 裳華房)を参照してほしい。 | ||
Revision as of 09:27, 9 June 2011
Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
パーコレーションとは
パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率pで占有されるときに生成されるクラスターを解析する。 様々な格子において、確率 p がある閾値 に達すると、無限に大きなクラスターが存在し始める(臨界現象)。この値を浸透閾値 (percolation threshold) と呼ぶ。浸透閾値 はほとんどの場合について厳密解が求まっていないが、数値シミュレーション等で解析されている。
上記のように格子点が確率 p で占有される過程を、正確にはサイト過程と呼ぶ。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率 p で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼ぶ。
主な浸透閾値 (*は厳密解) | ||
---|---|---|
格子の種類 | サイト | ボンド |
蜂の巣 | 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 の異なるクラスターの数を であらわす。2次元格子の場合、以下のようになる。
母関数とよく使う記法
これからよく使う記法を母関数を使ってまとめておく。
- ある格子点が、大きさs、周縁tのクラスターに含まれる確率
- ある格子点が、s-クラスターに含まれる確率
- ある格子点が、有限の大きさのクラスターに含まれる確率
- ある格子点が、無限大のクラスターに含まれる確率 (=浸透確率)
- ある格子点が含まれる、有限の大きさのクラスターの平均サイズ
- 個々のクラスターを1回だけ数えたときの、クラスターの平均サイズ
一次元の場合
一次元の場合は、無限に長い直線上に、定められた間隔で格子点をおく。 無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないのでである。 また、周縁サイズは常にの1パターンのみとなる。 この簡便さから、多くの問いに対して厳密解を求めることができる。
- 母関数
- ある格子点が、s-クラスターに含まれる確率
- ある格子点が、有限の大きさのクラスターに含まれる確率
- ある格子点が、無限大のクラスターに含まれる確率 (=浸透確率)
- ある格子点が含まれる、有限の大きさのクラスターの平均サイズ
- 個々のクラスターを1回だけ数えたときの、クラスターの平均サイズ
相関関数と相関距離
ある占有された格子点から だけ離れた格子点が同じクラスターに属する確率を であらわし、相関関数とよぶ。
ここで。この を相関距離という。
大まかにいうと、相関距離はクラスターの差し渡しに比例する。一次元の場合は、 1列に並ぶだけなので が成立する。また も成立する。
- 証明
- 一次元の場合、r ステップ離れた箇所まで全ての点が占有されねばならないから が成立。
- 。(証明終)
木またはベーテ格子の場合
次数が一定で無限に大きな木をベーテ格子と呼ぶ(有限の場合はケーリー木と呼んでもよい)。 磁性を扱う方法の一つであるベーテ近似によりこの木の厳密解が求まるため、ベーテ格子と呼ぶようになった。 一次元の場合は、次数が2のベーテ格子と考えられる。
次数が d の木の場合、原点は d 本の枝を持つ。 残りの点は通ってきた点のほかに 本の枝を持ち、それらの先に確率 p で占有される格子点が存在する。 先に進める確率は になるので、無限大のクラスターが存在し始める値は 。 つまり各点からみて平均 本つながっていれば、無限に大きなクラスターになる。 逆に、これより低い p の値では、無限に大きなクラスターは存在しない。 以降、簡単のため に話を限定する。 母関数を求めるのはややこしいが、興味のある人は「パーコレーションの科学」(小田垣 孝著 裳華房)を参照してほしい。
浸透確率 P∞
ある格子点が、無限大のクラスターに含まれる確率 (=浸透確率)を求めよう。 のとき(無限に大きいクラスターがあるとき)、任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率をQとする。 ある近接した格子点から外に無限遠へつながらない確率は、その格子点が占有されていないか、占有されてもその先でつながらない確率を足したもの。 これはQに等しいはずなので。これを解くと。
の場合は無限遠に決してつながらず、 のときの に対応する。 のとき、 を考える。 原点が占有されていても無限遠につながらない確率は 。 これより。
まとめると
F | p | |
P∞ | 0 |
クラスターの平均サイズ S
ある枝の先につながっている格子点数の期待値を と書く。 まず の場合を考える。 どの格子点もサイズが無限大のクラスターには属さない。 従って、枝の先にある格子点が占有されていればその格子点プラス二つの枝の平均サイズが付け加わるから 。 これを解くと 。 従って、ある頂点が属するクラスターの平均サイズは 。 この議論は容易に一般化できる。 次数 d の場合 なら 。
- ↑ 同半径の球を敷き詰めたときの最密充填