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 1: / Line 1: @@
-==ランダムグラフでのパーコレーション==
+{{Lecture/Header}}
-ランダムグラフは、ある次数分布に従うツリーとみなすことができる。
+==グラフ上のパーコレーション==
-これを扱うには、母関数という概念を利用する。
-==母関数==
+グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。ここでの議論は[[Aritalab:Lecture/Basic/GF_DegreeDistribution|母関数を使った説明]]もあります。
-ある分布<math>p(k)</math>の母関数(generating function)を<math>\textstyle G_0(x) = \Sigma_{k=0}^{\infty}p(k)x^k</math>と定義する。確率<math>p(k)</math>は全部足すと1なので、<math>\textstyle G_0(1) = \Sigma_{k=0}^{\infty}p(1)1^k = 1</math>が成立する。また<math>\textstyle G_0'(1) = \Sigma_{k=0}^{\infty}p(k)kx^{(k-1)} \bigg|_{x=1} = \Sigma kp(k) = \langle k \rangle</math>、<math>\textstyle G_0''(1) = \Sigma_{k=0}^{\infty}p(k)k(k-1)x^{(k-2)} \bigg|_{x=1} = \Sigma k(k-1)p(k) = \langle k^2 \rangle - \langle k \rangle</math>となる。
-==次数分布の母関数==
+あるネットワークの平均次数が <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(x)</math>になる。ある頂点vの隣にある頂点wの次数分布はもはや<math>p(k)</math>ではなく、母関数も異なる。辺をランダムに1本選んだとき、もう片方にある端点がどんな次数になっているかをあらわす分布が必要である。辺をランダムに選んだ先には、次数が大きい点が存在する確率が高い。つまり、もう片側にある端点の次数が<math>k</math>になる確率は、辺の数で重みをつけた次数分布に比例して<math>\textstyle kp(k)/\Sigma_j jp(j)</math>となる（分母は正規化定数）。よってある頂点vの隣にある頂点wの次数分布の母関数は<math>\textstyle \Sigma_{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>となる。
-母関数においては、次数<math>k</math>に対して<math>x^k</math>が対応することに注意しよう。頂点vの先にwがついているとき、wが持つ辺の一つはvに戻るため、外側に伸びる辺は<math>k-1</math>になる。そのときの母関数は上の式を<math>x</math>で割ればよく<math>G_e(x) = \frac{G'_v(x)}{G'_v(1)}</math>と書ける。
+==パーコレーションの起こりやすさ==
+いかなる次数分布でも、<math>\langle k^2 \rangle</math>が<math>\langle k \rangle</math>に比して大きいと、低い浸透確率で相転移が起こります。
-相転移が起きるのは頂点から伸びていく辺の期待値が1をちょうど超えるとき、つまり<math>G_e'(1) = \frac{G'_v(1)}{G'_v(1)} = 1</math>のとき。すなわち<math>\langle k^2 \rangle = 2 \langle k \rangle</math>のときになる。別の書き方では<math>\Sigma k(k-2)p(k) = 0</math>だが、この和のうち負の値になるのは<math>k=1</math>のときだけ、つまり行き止まりが極端に多くない限り、連結成分は繋がって無限に大きくなることを意味している。
+===格子グラフ、Erdosブラフ===
+次数が一定の場合、<math>\langle k^2 \rangle = \langle k \rangle^2</math> です。すなわち、<math>q_c = 1 / \langle k \rangle</math> となります。
+次数分布がポアソン分布をなす場合、平均と分散は等しく　<math>E[k] = V[k] = \langle k \rangle </math> になります。
+このとき <math>\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle </math> です。この場合も格子グラフとほぼ同じで、平均次数に反比例して浸透確率が下がります。
+===スケールフリーネットワーク===
+次数の分布が、べき分布 <math>p(k)=Ck^{-\gamma}</math> のときをかんがえましょう。
+ここで <math>\zeta(\gamma)\ </math> はリーマンゼータ関数とします。
+<math>
+\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)}
+</math>
+この値は<math>\gamma \leq 3</math>のときに発散します。また <math>\gamma</math> が大きくなると <math> k=1 </math> の項が大きな要素を占めるのでほとんど 1 に近づきます。
 <!----
+別の書き方では<math>\Sigma k(k-2)p(k) = 0</math>だが、この和のうち負の値になるのは<math>k=1</math>のときだけ、つまり行き止まりが極端に多くない限り、連結成分は繋がって無限に大きくなることを意味している。
 ==連結成分のサイズの母関数==
 ランダムに選んだ辺から出発したときの連結成分のサイズの分布を<math>H_e(x)</math>、ランダムに選んだ頂点を含む連結成分のサイズの分布を<math>H_v(x)</math>と書こう。辺を選んだとき、連結成分が先に広がるかどうかはもう片側にある端点の次数に依存し、その分布は<math>\textstyle kp(k)/\Sigma_j jp(j)</math>である。それぞれの先からも辺が伸びていくため
@@ Line 21: / Line 37: @@
 連結成分のサイズの期待値は<math>H_v'(1) = G_v(H_e(1)) + G_v'(1)H_e'(1)=</math>
----->
-==パーコレーション==
 パーコレーションにおいては、確率<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>のあたりである。<math>\langle k^2 \rangle</math>が大きいと非常に低いパーコレーション確率でも相転移が起こる。つまり感染率が低くてもネットワーク全体に蔓延する。この値はべき分布<math>p(k)=ck^{-\gamma}</math>のときおよそ<math>\Sigma_kk^2p(k) = c\Sigma k^{2-\gamma}</math>になるため、<math>\gamma</math>が3以下であればパーコレートする。
+大雑把に言うと相転移を起こすのは<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