Aritalab:Lecture/NetworkBiology/Percolation on Graph

Latest revision as of 12:19, 6 August 2016

[edit] グラフ上のパーコレーション

グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。ここでの議論は母関数を使った説明もあります。

あるネットワークの平均次数が <k> で与えられるとき、隣接点の平均次数は $\textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}$ になります。この本数のうち、確率 q でサイトが ON になる場合、隣接点の周りで占有される頂点数は $q \textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}$ になります。これが 1 を上回る場合に相転移をおこすので、臨界確率 $q_c = \textstyle \frac{1}{\langle k^2 \rangle / \langle k \rangle - 1 }$ が得られます。つまり、<k²> / <k> のバランスに臨界確率が左右されるということです。

[edit] パーコレーションの起こりやすさ

いかなる次数分布でも、 $\langle k^2 \rangle$ が $\langle k \rangle$ に比して大きいと、低い浸透確率で相転移が起こります。

[edit] 格子グラフ、Erdosブラフ

次数が一定の場合、 $\langle k^2 \rangle = \langle k \rangle^2$ です。すなわち、 $q_c = 1 / \langle k \rangle$ となります。

次数分布がポアソン分布をなす場合、平均と分散は等しく　 $E[k] = V[k] = \langle k \rangle$ になります。このとき $\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle$ です。この場合も格子グラフとほぼ同じで、平均次数に反比例して浸透確率が下がります。

[edit] スケールフリーネットワーク

次数の分布が、べき分布 $p(k)=Ck^{-\gamma}$ のときをかんがえましょう。ここで $\zeta(\gamma)\$ はリーマンゼータ関数とします。

$\frac{\langle k^2 \rangle}{\langle k \rangle} = \frac{\Sigma_kk^2p(k)}{\Sigma_kkp(k)} = \frac{\Sigma k^{2-\gamma}}{ \Sigma k^{1-\gamma}} = \frac{\zeta(\gamma - 2)}{\zeta(\gamma - 1)}$

この値は $\gamma \leq 3$ のときに発散します。また $\gamma$ が大きくなると $k=1$ の項が大きな要素を占めるのでほとんど 1 に近づきます。

@@ Line 3: / Line 3: @@
 ==グラフ上のパーコレーション==
-グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみよう。
+グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。ここでの議論は[[Aritalab:Lecture/Basic/GF_DegreeDistribution|母関数を使った説明]]もあります。
-ここでは母関数という概念を利用する。
-==次数分布の母関数==
+あるネットワークの平均次数が <k> で与えられるとき、隣接点の平均次数は <math>\textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}</math> になります。この本数のうち、確率 q でサイトが ON になる場合、隣接点の周りで占有される頂点数は <math>q \textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}</math>  になります。これが 1 を上回る場合に相転移をおこすので、臨界確率 <math>q_c = \textstyle \frac{1}{\langle k^2 \rangle / \langle k \rangle - 1 }</math>  が得られます。つまり、<k<sup>2</sup>> / <k> のバランスに臨界確率が左右されるということです。
-グラフの次数分布<math>p(k)</math>を与えられたとき、その母関数は
-<math>G_v(z) = \sum p(k) z^k</math>
+==パーコレーションの起こりやすさ==
-しかし、頂点''v''の隣にある頂点''w''の次数分布はもはや<math>p(k)</math>ではない。
+いかなる次数分布でも、<math>\langle k^2 \rangle</math>が<math>\langle k \rangle</math>に比して大きいと、低い浸透確率で相転移が起こります。
-辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えよう。
-選ばれた辺の先には、他の点が等確率でくることはない。次数の大きい点のほうが、次数に比例して存在する確率が高くなるだろう。
-つまり、もう片側にある端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した<math>\textstyle kp(k)/\Sigma_j jp(j)</math>となる（分母は正規化定数）。
-よってある頂点''v''の隣にある頂点''w''の次数分布の母関数は
-<math>\sum_{k=0}^{\infty}x^k\frac{kp(k)}{\Sigma_jjp(j)} = x\frac{\Sigma_k kx^{(k-1)}p(k)}{\Sigma_jjp(j)} = x\frac{G'_v(x)}{G'_v(1)}</math>
+===格子グラフ、Erdosブラフ===
+次数が一定の場合、<math>\langle k^2 \rangle = \langle k \rangle^2</math> です。すなわち、<math>q_c = 1 / \langle k \rangle</math> となります。
-母関数においては、次数<math>k</math>に対して<math>x^k</math>が対応する。
+次数分布がポアソン分布をなす場合、平均と分散は等しく　<math>E[k] = V[k] = \langle k \rangle </math> になります。
-頂点''v''の先に''w''がついているとき、''w''から''v''以外に伸びる辺数に注目しよう。
+このとき <math>\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle </math> です。この場合も格子グラフとほぼ同じで、平均次数に反比例して浸透確率が下がります。
-''v''から''w''への辺1本を除いた、''w''に関する母関数は上の式を<math>x</math>で割ればよい。
-<math>G_w(x) = \frac{G'_v(x)}{G'_v(1)}</math>
+===スケールフリーネットワーク===
-==占有される頂点の母関数==
+次数の分布が、べき分布 <math>p(k)=Ck^{-\gamma}</math> のときをかんがえましょう。
+ここで <math>\zeta(\gamma)\ </math> はリーマンゼータ関数とします。
-パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときである。
-ただし、このときの母関数はグラフ全体の次数分布を示す<math>G_v</math>ではなく、占有された頂点のみによる部分ネットワークの母関数である。
-したがって、母関数を区別して<math>F_v</math>と記そう。''F''と''G''の関係は、各頂点が確率''q''で占有されるため''G''と''F''の次数平均をそれぞれ<math>\langle k \rangle</math>, <math>\langle l \rangle</math>
-と書くと
 <math>
-\begin{align}
+\frac{\langle k^2 \rangle}{\langle k \rangle} = \frac{\Sigma_kk^2p(k)}{\Sigma_kkp(k)} = \frac{\Sigma k^{2-\gamma}}{ \Sigma k^{1-\gamma}} = \frac{\zeta(\gamma - 2)}{\zeta(\gamma - 1)}
-\langle l \rangle &= q \langle k \rangle \\
-\end{align}
 </math>
-この関係から
+この値は<math>\gamma \leq 3</math>のときに発散します。また <math>\gamma</math> が大きくなると <math> k=1 </math> の項が大きな要素を占めるのでほとんど 1 に近づきます。
-<math>
-\begin{align}
-F'_v(1) &= q G'_v(1) = q \langle k \rangle \\
-F''_v(1) &= q^2G''_v(1) = q^2 (\langle k^2 \rangle - \langle k \rangle)
-\end{align}
-</math>
-相転移が起きるのは<math>F_w'(1) = 1</math>のときだから
-<math>
-F'_w(1) = \frac{F''_v(1)}{F'_v(1)} = 1
-</math>
-代入すると
-<math>
-q_c = \frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle} - 1}
-</math>
-すなわち、<math>\langle k^2 \rangle</math>が大きく<math>\langle k \rangle</math>を上回るとき、<math>q_c</math>は小さくなる。
-==パーコレーション==
-いかなる次数分布でも、<math>\langle k^2 \rangle</math>が<math>\langle k \rangle</math>に比して大きいと、低いパーコレーション確率で相転移が起こることを見た。
-===ランダムグラフの場合===
-ランダムグラフの場合は次数分布がポアソン分布になる。このとき<math>\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle </math>になるので
-<math>q_c = 1 / \langle k \rangle</math>
-すなわち、平均次数が大きくなるほどパーコレートしやすくなる。
-===スケールフリーネットワークの場合===
-べき分布<math>p(k)=ck^{-\gamma}</math>のとき
-<math>
-\langle k^2 \rangle = \Sigma_kk^2p(k) = c\Sigma k^{2-\gamma}
-</math>
-この値は<math>\gamma　\leq 3</math>のときに発散する。有限のネットワークではその値も有限だが、大きな値になるために
-非常に低い値でパーコレートする。
 <!----
@@ Line 96: / Line 41: @@
 パーコレーションにおいては、確率<math>(1-q)</math>で辺が繋がらなくなる。実効的な次数が<math>\bar{k}</math>になる確率は<math>\bar{p}(\bar{k}) = \Sigma_{k=\bar{k}}^{\infty}p(k) \tbinom{k}{\bar{k}}q^{\bar{k}}(1-q)^{k-\bar{k}}</math>である。
-<!----
 このとき<math>\langle \bar{k} \rangle = \langle k \rangle q</math>、<math>\langle \bar{k^2} \rangle = \langle k^2 \rangle + \langle k \rangle q (1-q)</math>になる。
 大雑把に言うと相転移を起こすのは<math>\langle k^2 \rangle q^2= 2 \langle k \rangle q</math>のとき、つまり<math>q = 2 \langle k \rangle / \langle k^2 \rangle</math>のあたりである。
+---->
-つまり感染率が低くてもネットワーク全体に蔓延する。
---->

Aritalab:Lecture/NetworkBiology/Percolation on Graph

Latest revision as of 12:19, 6 August 2016

Contents

[edit] グラフ上のパーコレーション

[edit] パーコレーションの起こりやすさ

[edit] 格子グラフ、Erdosブラフ

[edit] スケールフリーネットワーク

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox