Aritalab:Lecture/NetworkBiology/Percolation

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m (母関数とよく使う記法)
m (ボンド過程とサイト過程)
Line 5: Line 5:
 
パーコレーション(浸透)理論 (percolation theory) は、非常に大きな格子において各格子点が周囲とは全く独立に確率''p''で占有されるときに生成されるクラスターを解析する。
 
パーコレーション(浸透)理論 (percolation theory) は、非常に大きな格子において各格子点が周囲とは全く独立に確率''p''で占有されるときに生成されるクラスターを解析する。
 
様々な格子において、確率''p''がある閾値<math>p_c</math>に達すると、無限に大きなクラスターが存在し始めることが知られている(臨界現象)。この値を浸透閾値 (percolation threshold) と呼ぶ。浸透閾値<math>p_c</math>はほとんどの場合について厳密解が求まっていないが、数値シミュレーション等で解析されている。
 
様々な格子において、確率''p''がある閾値<math>p_c</math>に達すると、無限に大きなクラスターが存在し始めることが知られている(臨界現象)。この値を浸透閾値 (percolation threshold) と呼ぶ。浸透閾値<math>p_c</math>はほとんどの場合について厳密解が求まっていないが、数値シミュレーション等で解析されている。
 
===ボンド過程とサイト過程===
 
  
 
上記のように格子点が確率''p''で占有される過程は正確にはサイト過程と呼ぶ。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率''p''で開閉されると考えて生成するクラスターを解析する場合は、ボンド過程と呼ぶ。
 
上記のように格子点が確率''p''で占有される過程は正確にはサイト過程と呼ぶ。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率''p''で開閉されると考えて生成するクラスターを解析する場合は、ボンド過程と呼ぶ。
  
{| class="wikitable"
+
{| class="wikitable" style="float:right"
 
|-
 
|-
 
!colspan=3| 主な浸透閾値<math>p_c</math> (*は厳密解)
 
!colspan=3| 主な浸透閾値<math>p_c</math> (*は厳密解)
Line 38: Line 36:
 
| d=7 超立方 || 0.088951 || 0.078675
 
| d=7 超立方 || 0.088951 || 0.078675
 
|}
 
|}
</center>
 
  
 
==クラスターと周縁==
 
==クラスターと周縁==

Revision as of 21:59, 11 June 2010

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

Contents

パーコレーションとは

パーコレーション(浸透)理論 (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を使ってまとめておく。

1. ある格子点が、大きさs、周縁tのクラスターに含まれる確率
\textstyle p_{s,t} = a_{s,t} p^s (1-p)^t
2. ある格子点が、s-クラスターに含まれる確率
\textstyle P_s = \sum_t p_{s,t}
3. ある格子点が、有限の大きさのクラスターに含まれる確率
\textstyle F = \sum_{s,t} p_{s,t} = \sum_s P_s = A(p, 1-p)
4. ある格子点が、無限大のクラスターに含まれる確率 (=浸透確率)
\textstyle P_{\infty} = p - F
5. ある格子点が含まれる、有限の大きさのクラスターの平均サイズ
S = \frac{\sum_{s,t} s p_{s,t}}{F} = \frac{\sum_s s P_s}{\sum_s P_s} =  \Bigg[ x\frac{\partial}{\partial x}\log A(x,y) \Bigg]_{x=p,\ y=1-p}
6. 個々のクラスターを1回だけ数えたときの、クラスターの平均サイズ
\langle s \rangle = \frac{\sum_s P_s}{\sum_s (1/s)P_s}

一次元の場合

一次元の場合は、多くの問いに対して厳密解を求めることができる。 無限に長い直線上に、定められた間隔で格子点をおく。 無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないのでp_c=1である。

大きさsのクラスター

大きさがsのクラスター(s-クラスターと呼ぶ)が生じる確率はn_s = p^s(1-p)^2

ある点が、一つのs-クラスターに含まれる確率は、クラスター中のどの点に該当しても良いからFailed to parse (lexing error): s n_s

ある点が、どんなサイズでもよいからクラスターに含まれる確率はpなので、p = \sigma s n_s

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

あるクラスター中の点を考えたとき、属しているクラスターのサイズがsである確率はw_s = s n_s / p

クラスターの平均サイズは、全ての格子点を等確率に選んでそれが属する平均的サイズをかけたものに等しいから\textstyle \Sigma w_s s = \frac{(1-p)^2}{p} \Sigma s^2 p^s。 これは\textstyle \frac{1+p}{1-p}に等しい。つまりpが1に近づくとクラスターの平均サイズは発散する(あたりまえ)。

証明
補題 \textstyle \Sigma_ss^2p^s = \frac{p(1+p)}{(1-p)^3}
\textstyle \Sigma_ss^2p^s = (p\frac{d}{dp})^2\Sigma_sp^s = (p\frac{d}{dp})^2\frac{p}{1-p} = p\frac{d}{dp}\frac{p}{(1-p)^2} = p \frac{1+p}{(1-p)^3}

補題より、クラスターの平均サイズは\textstyle S = \frac{(1-p)^2}{p} \frac{p(1+p)}{(1-p)^3} = \frac{1+p}{1-p}。(証明終)

相関関数

ある占有された格子点からrだけ離れた格子点が同じクラスターに属する確率をg(r)であらわす。一般に\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。(証明終)

p^rpが閾値p_cに近いとき展開公式\textstyle \log(1-x) = -xを用いて\textstyle g(r) = exp(\frac{-r}{\xi})と書ける。ただし\textstyle \xi = -\frac{1}{\log(p)} = \frac{1}{1 - p} = \frac{1}{p_c-p}である。この\xiを相関距離といい、大まかにいってクラスターの差し渡しに比例する。また一次元の場合は、\textstyle S \varpropto \xi \ (p \rightarrow p_c)が成立している。

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

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

パーコレーション確率 P

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

先に進める確率は(d-1)pになるので、無限大のクラスターが存在し始める値は\textstyle p_c=\frac{1}{d-1}。これより低いpの値では、無限に大きなクラスターは決して存在しない。

p > p_cのとき(無限に大きいクラスターがあるとき)、任意に選んだ点が無限に広がるネットワークに属する確率P(パーコレーション確率)を求める。(一次元の場合はp_c = 1のときに限って無限に大きなクラスターが存在できるため、Pは考えなかった。)

簡単のためd=3 (p_c = 1/2)に限定する。

任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率をQとする。

ある近接した格子点から外に無限遠へつながらない確率は、その格子点が占有されていないか、占有されてもその先でつながらない確率を足したもの。

これはQに等しいはずなのでQ = (1-p) + pQ^2。これを解くと\textstyle Q = 1, \frac{1-p}{p}

Q=1の場合は無限遠に決してつながらないからP=0。したがってQ = \frac{1-p}{p}のみを考える。

原点が占有されていても無限遠につながらない確率はp-P = pQ^3

式変形して\textstyle P = p(1-Q^3) = p(1 - (\frac{1-p}{p})^3)

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

ある枝に属している格子点の数の平均をTと書く。

近接する格子点が占有されていればその格子点プラス二つの枝の平均が付け加わるのでT = (1-p)0 +p(1+2T)

これを解くとp<1/2のときに限りT=p/(1-2p)

原点が属するクラスターの平均サイズは\textstyle 1 + 3T = \frac{1+p}{1-2p} = \frac{1+p}{2(p_c - p)}。ここでもS \varpropto (p_c - p)

一次元と木のまとめ


Cite error: <ref> tags exist, but no <references/> tag was found
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox