Aritalab:Lecture/NetworkBiology/Percolation

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
(パーコレーションとは)
m (パーコレーションとは)
 
(35 intermediate revisions by one user not shown)
Line 3: Line 3:
 
==パーコレーションとは==
 
==パーコレーションとは==
  
パーコレーション(浸透)理論は、非常に大きな格子において各格子点が周囲とは全く独立に確率''p''で占有されるときに生成されるクラスターを解析する。
+
パーコレーション(浸透)理論 (percolation theory) では、非常に大きな格子において各格子点が周囲とは全く独立に確率 p で占有されるときに生成されるクラスターを解析します。
様々な格子において、確率''p''がある閾値<math>p_c</math>に達するときに無限に大きなクラスターが存在することが知られている(臨界現象)。この値を浸透閾値と呼ぶ。
+
様々な格子において、確率 p がある閾値 p<sub>c</sub> に達すると、無限に大きなクラスターが存在し始めます。これを臨界現象といい、臨界点を浸透閾値 (percolation threshold) と呼びます。ある格子点が無限大のクラスターに含まれる確率を浸透確率 (percolation probability) とよびます。浸透閾値 p<sub>c</sub> はほとんどの場合について厳密解が求まっていませんが、数値シミュレーション等で解析されています。
  
浸透閾値<math>p_c</math>はほとんどの場合について厳密解が求まっていないが、数値シミュレーション等で解析されている。
+
上記のように格子点が確率 p で占有される過程を、正確にはサイト過程と呼びます。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率 p で開閉されると考えて生成するクラスターを解析する場合を、ボンド過程と呼びます。
  
===ボンド過程とサイト過程===
+
{| class="wikitable" style="float:right"
 
+
上記のように格子点が確率''p''で占有される過程は正確にはサイト過程と呼ぶ。これに対して、格子点と格子点を結ぶ辺(ボンド)が確率''p''で開閉されると考えて生成するクラスターを解析する場合は、ボンド過程と呼ぶ。
+
 
+
無限に大きな格子状の上で無限大のクラスターが生じ始める確率<math>p_c</math>が浸透閾値である。
+
 
+
<center>
+
主な浸透閾値<math>p_c</math>。*は厳密解をあらわす。
+
{| class="wikitable"
+
 
|-
 
|-
! 格子の種類 || サイト || ボンド
+
!colspan=4| 格子の主な浸透閾値 p<sub>c</sub> (*のみ厳密解。<br/>ほとんどの場合解析的に解けない。)
 
|-
 
|-
| 蜂の巣 || 0.697043 || 0.65271<sup>*</sup>
+
! 格子の種類 || 配位数 || サイト || ボンド
 
|-
 
|-
| 正方 || 0.5927462 || 1/2 <sup>*</sup>
+
| 蜂の巣 || 3 || 0.697043 || 0.65271<sup>*</sup>
 
|-
 
|-
| 三角 || 1/2 <sup>*</sup> || 0.34729<sup>*</sup>
+
| 正方 || 4 || 0.5927462 || 1/2 <sup>*</sup>
 
|-
 
|-
| ダイヤモンド || 0.4301 || 0.3893
+
| 三角 || 6 || 1/2 <sup>*</sup> || 0.34729<sup>*</sup>
 
|-
 
|-
| 単純立方 || 0.311608 || 0.248813
+
| ダイヤモンド || 4 || 0.4301 || 0.3893
 
|-
 
|-
| 体心立方 || 0.245691 || 0.180287
+
| 単純立方 || 6 || 0.311608 || 0.248813
 
|-
 
|-
| 面心立方<ref>同半径の球を敷き詰めたときの最密充填</ref> || 0.199236 || 0.120163
+
| 体心立方 || 8 || 0.245691 || 0.180287
 
|-
 
|-
| d=4 超立方 || 0.196885 || 0.160131
+
| 面心立方<ref>同半径の球を敷き詰めたときの最密充填</ref> || 12 || 0.199236 || 0.120163
 +
|}
 +
<!---
 
|-
 
|-
| d=5 超立方 || 0.140797 || 0.118172
+
| d=4 超立方 || || 0.196885 || 0.160131
 
|-
 
|-
| d=6 超立方 || 0.109018 || 0.094202
+
| d=5 超立方 || || 0.140797 || 0.118172
 
|-
 
|-
| d=7 超立方 || 0.088951 || 0.078675
+
| d=6 超立方 || || 0.109018 || 0.094202
|}
+
|-
</center>
+
| d=7 超立方 || || 0.088951 || 0.078675
 +
--->
  
==一次元の場合==
+
==クラスター・周縁という概念==
一次元の場合は、多くの問いに対して厳密解を求めることができる。
+
各格子点が確率 ''p'' で占有されるとし、占有された格子点の集まりをクラスターと呼びます。特に、大きさが ''s'' のクラスターを ''s-''クラスターと呼びます。クラスターの周囲の格子点は空でなくてはなりません。クラスターに隣接する空の格子点群を周縁 (perimeter) と呼びます。クラスターが大きくなると内部にも周縁が存在しうるので、周縁と周囲は異なることに注意します。
  
無限に長い直線上に、定められた間隔で格子点をおき、各点は確率''p''で占有されているとする。占有された格子点の集まりをクラスターと呼ぶ。
+
ある格子点を含む、大きさ ''s'' 、周縁 ''t'' の異なるクラスターの数を <math>a_{s,t}</math> であらわします。2次元格子の場合は以下のようになります。占有点を黒、非占有点を白、注目している格子点を灰色であらわしています。
  
無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないので<math>p_c=1</math>である。
+
<math>a_{1,4} = 1 \quad a_{2,6} = 4 \quad a_{3,8} = 6 \quad a_{3,7} = 12 </math>
  
===大きさ''s''のクラスター===
+
[[File:Lecture-NetworkBiology-Percolation.png]]
大きさが''s''のクラスター(''s-''クラスターと呼ぶ)が生じる確率は<math>n_s = p^s(1-p)^2</math>。
+
  
ある点が、一つの''s-''クラスターに含まれる確率は、クラスター中のどの点に該当しても良いから<math>s n_s</math>。
+
==一次元の場合==
  
ある点が、どんなサイズでもよいからクラスターに含まれる確率は''p''なので、<math>p = \sigma s n_s</math>
+
無限に長い直線上に一定間隔で格子点がある場合を考えます。
 +
無限に伸びるクラスターができるためには全ての格子点が占有されなくてはならないので、浸透閾値 p<sub>c</sub> = 1、周縁サイズは常に t = 2 です。この簡便さから、多くの問いに対して厳密解を求められます。
  
===クラスターの平均サイズ ''S''===
 
  
あるクラスター中の点を考えたとき、属しているクラスターのサイズが''s''である確率は<math>w_s = s n_s / p</math>
+
* ある格子点が、s-クラスターに含まれる確率
 +
ある格子点は、大きさ s のクラスターのどの位置にもなりうるので s 通りの可能性があります。
 +
:<math>\textstyle P_s = s p_{s,t} = s p^s (1-p)^2</math>
 +
* 浸透確率(格子点が無限大のクラスターに含まれる確率)、クラスターの平均サイズ
 +
{| class="wikitable"
 +
|valign="top"|
 +
|
 +
; p < p<sub>c</sub> = 1 の場合
 +
|
 +
; p = p<sub>c</sub> = 1 の場合
 +
|-
 +
|valign="top"|
 +
浸透確率
 +
|
 +
: 0
 +
|valign="top"|
 +
: 1
 +
|-
 +
|valign="top"|
 +
平均サイズ
 +
|
 +
:( 1 + p ) / ( 1 - p )
 +
|
 +
: 0
 +
|}
  
クラスターの平均サイズは、全ての格子点を等確率に選んでそれが属する平均的サイズをかけたものに等しいから<math>\textstyle \Sigma w_s s = \frac{(1-p)^2}{p} \Sigma s^2 p^s</math>
+
平均サイズの計算は説明が必要でしょう。それぞれの s-クラスターが出現する確率 P<sub>s</sub> にサイズ s をかけたものを、s-クラスターが出現する確率の総和で割れば平均サイズが求まります。
これは<math>\textstyle \frac{1+p}{1-p}</math>に等しい。つまり<math>p</math>が1に近づくとクラスターの平均サイズは発散する(あたりまえ)。
+
<math>
 +
\begin{align}
 +
S &= \frac{\sum_s s P_s}{\sum_s P_s}
 +
\end{align}
 +
</math>
 +
分母は各点がクラスターに含まれる確率に等しいので p になります。面倒なのは分子の計算です。
  
;証明
+
<math>
:補題 <math>\textstyle \Sigma_ss^2p^s = \frac{p(1+p)}{(1-p)^3}</math>
+
\begin{align}
:<math>\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}</math>
+
\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}
 +
</math>
  
補題より、クラスターの平均サイズは<math>\textstyle S = \frac{(1-p)^2}{p} \frac{p(1+p)}{(1-p)^3} = \frac{1+p}{1-p}</math>。(証明終)
+
お疲れ様でした。
  
===相関関数===
+
==木またはベーテ格子の場合==
ある占有された格子点から<math>r</math>だけ離れた格子点が同じクラスターに属する確率を<math>g(r)</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>。(証明終)
+
ベーテ格子はサイクルを持たない一次元の場合は、次数が2のベーテ格子です。
  
式<math>p^r</math>は<math>p</math>が閾値<math>p_c</math>に近いとき展開公式<math>\textstyle \log(1-x) = -x</math>を用いて<math>\textstyle g(r) = exp(\frac{-r}{\xi})</math>と書ける。ただし<math>\textstyle \xi = -\frac{1}{\log(p)} = \frac{1}{1 - p} = \frac{1}{p_c-p}</math>である。この<math>\xi</math>を相関距離といい、大まかにいってクラスターの差し渡しに比例する。また一次元の場合は、<math>\textstyle S \varpropto \xi \ (p \rightarrow p_c)</math>が成立している。
+
;特徴
 +
* 次数が d の木の場合、原点は d 本の枝を持つ。
 +
* 残りの点は通ってきた点のほかに d &minus; 1 本の枝を持ち、それらの先に確率 p で占有される格子点が存在する。
  
 +
先に進める確率は (d &minus; 1) p になるので、無限大のクラスターが存在し始める値は p<sub>c</sub> = 1 / (d - 1)、つまり各点に平均 d / (d - 1) 本の枝があれば、無限に大きなクラスターが存在します。
 +
逆に、これより低い p の値では、無限に大きなクラスターは存在しません。
 +
以降、簡単のため d = 3 ( p<sub>c</sub> = 1/2 ) に話を限定します。
  
==木またはベーテ格子の場合==
+
=== d = 3 の木===
次数が一定で無限に大きな木をベーテ格子と呼ぶ(有限の場合はケーリー木と呼んでもよい)。
+
ここまでの議論から、浸透閾値は 1/2 であり、浸透確率が 1/2 を超えると、その頂点にたどり着いた枝を除いた残り 2 本のうちどちらかがつながっているから、無限大のクラスターが存在します。
磁性を扱う方法の一つであるベーテ近似によりこの木の厳密解が求まるためにベーテ格子と呼ぶようになった。
+
  
===パーコレーション確率 ''P''===
+
===格子点が無限大のクラスターに含まれる確率 P<sub>∞</sub>===
次数が''d''の木の場合、原点は''d''本の枝を持つ。残りの点は通ってきた点のほかに''d-1''本の枝を持ち、それらの先に確率''p''で占有される格子点が存在する。
+
p > p<sub>c</sub> = 1 / 2 のとき(無限に大きいクラスターがあるとき)、任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率を Q と書きます。
 +
ある近接した格子点から外に無限遠へつながらない確率は、その格子点が占有されていないか、占有されてもその先でつながらない確率を足したもの。
 +
これは Q に等しいはずなので
  
先に進める確率は''(d-1)p''になるので、無限大のクラスターが存在し始める値は<math>\textstyle p_c=\frac{1}{d-1}</math>。これより低い''p''の値では、無限に大きなクラスターは決して存在しない。
+
:Q = (1 - p) + p Q<sup>2</sup>
  
''p > p_c''のとき(無限に大きいクラスターがあるとき)、任意に選んだ点が無限に広がるネットワークに属する確率<math>P</math>(パーコレーション確率)を求める。(一次元の場合は<math>p_c = 1</math>のときに限って無限に大きなクラスターが存在できるため、<math>P</math>は考えなかった。)
+
を満たします。これを解くと Q = 1, (1 - p) / p。
  
簡単のため<math>d=3 (p_c = 1/2)</math>に限定する。
+
* Q = 1 の場合
 +
無限遠に決してつながらず、p < 1/2 のときに対応します。
 +
* Q = (1 - p) / p の場合
 +
p > 1/2 に相当します。 原点が占有されていても無限遠につながらない確率は
 +
: p  -P<sub>∞</sub> = p Q<sup>3</sup>
  
任意の格子点が、それから始まる枝のうち一つを通しては無限遠につながらない確率を''Q''とする。
+
これより 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"
 +
! || <math>\textstyle p < \frac{1}{2}</math> || <math>\textstyle p > \frac{1}{2}</math>
 +
|-
 +
| 有限のクラスターに含まれる確率  || p || <math>\textstyle \frac{(1-p)^3}{p^2}</math>
 +
|-
 +
| 無限大のクラスターに含まれる確率  || 0 || <math>\textstyle p - \frac{(1-p)^3}{p^2}</math>
 +
|}
  
これは''Q''に等しいはずなので<math>Q = (1-p) + pQ^2</math>。これを解くと<math>\textstyle Q = 1, \frac{1-p}{p}</math>。
+
===クラスターの平均サイズ S===
 +
ある枝の先につながっている格子点数の期待値を T とします。
 +
まず p < p<sub>c</sub> = 1/2 の場合を考えます。
 +
どの格子点もサイズが無限大のクラスターには属しません。(そうしないと平均サイズが計算できない。)
 +
枝の先にある格子点が占有されていれば、その格子点プラス二つの枝の平均サイズが付け加わるので
  
<math>Q=1</math>の場合は無限遠に決してつながらないから<math>P=0</math>。したがって<math>Q = \frac{1-p}{p}</math>のみを考える。
+
: T = (1 - p) 0 + p (1 + 2T)
  
原点が占有されていても無限遠につながらない確率は<math>p-P = pQ^3</math>。
+
これを解いて T = p / (1 - 2p) です。従って、ある頂点が属するクラスターの平均サイズは
  
式変形して<math>\textstyle P = p(1-Q^3) = p(1 - (\frac{1-p}{p})^3)</math>。
+
: S = 1 + 3T = (1 + p) / (1 - 2p)
  
===クラスターの平均サイズ ''S''===
+
まとめると
ある枝に属している格子点の数の平均を<math>T</math>と書く。
+
{| class ="wikitable" style="text-align:center"
 +
! || p < 1/2 || p >= 1/2
 +
|-
 +
| 平均サイズ || <math>\frac{(1+p)}{(1-2p)}</math> || <math>\infty</math>
 +
|}
  
近接する格子点が占有されていればその格子点プラス二つの枝の平均が付け加わるので<math>T = (1-p)0 +p(1+2T)</math>。
+
この議論は容易に一般化できます。次数 d の場合 p < p<sub>c</sub> = 1 / (d - 1) なら S = (1 + p) / (1 - dp) です。
  
これを解くと<math>p<1/2</math>のときに限り<math>T=p/(1-2p)</math>。
 
  
原点が属するクラスターの平均サイズは<math>\textstyle 1 + 3T = \frac{1+p}{1-2p} = \frac{1+p}{2(p_c - p)}</math>。ここでも<math>S \varpropto (p_c - p)</math>。
 
  
==一次元と木のまとめ==
+
;参考
 +
<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