Aritalab:Lecture/NetworkBiology/Percolation on Graph

Revision as of 10:10, 3 June 2010

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

グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみよう。ここでは母関数という概念を利用する。

次数分布の母関数

グラフの次数分布 $p(k)$ を与えられたとき、その母関数は

$G_v(z) = \sum p(k) z^k$

しかし、頂点vの隣にある頂点wの次数分布はもはや $p(k)$ ではない。辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えよう。選ばれた辺の先には、他の点が等確率でくることはない。次数の大きい点のほうが、次数に比例して存在する確率が高くなるだろう。つまり、もう片側にある端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した $\textstyle kp(k)/\Sigma_j jp(j)$ となる（分母は正規化定数）。よってある頂点vの隣にある頂点wの次数分布の母関数は

$\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)}$

母関数においては、次数 $k$ に対して $x^k$ が対応する。頂点vの先にwがついているとき、wからv以外に伸びる辺数に注目しよう。その母関数は上の式を $x$ で割ればよいから

$G_w(x) = \frac{G'_v(x)}{G'_v(1)}$

占有される頂点の母関数

パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときである。ただし、このときの母関数はグラフ全体の次数分布を示す $G_v$ ではなく、占有された頂点のみによる部分ネットワークの母関数である。したがって、母関数を区別して $F_v$ と記そう。FとGの関係は、各頂点が確率qで占有されるため

$\begin{align} F'_v(v) &= q G'_v(v) = q \langle k \rangle \\ F''_v(v) &= q^2G''_v(v) = q^2 (\langle k^2 \rangle - \langle k \rangle) \end{align}$

つまりGとFの次数平均と二乗平均をそれぞれ $\langle k \rangle$ , $\langle l \rangle$ と書くと

$\begin{align} \langle l \rangle &= q \langle k \rangle \\ \langle l^2 \rangle &= q^2 (\langle k^2 \rangle - \langle k \rangle) + q \langle k \rangle \end{align}$

相転移が起きるのは $F_w'(1) = 1$ のときだから

$F'_w(1) = \frac{F''_v(1)}{F'_v(1)} = 1$

に代入して

$q_c = \frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle} - 1}$

パーコレーション

いかなる次数分布でも、 $\langle k^2 \rangle$ が $\langle k \rangle$ に比して大きいと、低いパーコレーション確率で相転移が起こる。

ランダムグラフの場合

ランダムグラフの場合は次数分布がポアソン分布になる。このとき $\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle$ になるので

$q_c = 1 / \langle k \rangle$

すなわち、平均次数が大きくなるほどパーコレートしやすくなる。

スケールフリーネットワークの場合

べき分布 $p(k)=ck^{-\gamma}$ のとき

$\langle k^2 \rangle = \Sigma_kk^2p(k) = c\Sigma k^{2-\gamma}$

この値はFailed to parse (lexing error): \gamma　\leq 3 のときに発散する。有限のネットワークではその値も有限だが、大きな値になるために非常に低い値でパーコレートする。

@@ Line 1: / Line 1: @@
-==ランダムグラフでのパーコレーション==
+==グラフ上のパーコレーション==
-ランダムグラフは、ある次数分布に従うツリーとみなすことができる。
-これを扱うには、母関数という概念を利用する。
+グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみよう。
+ここでは母関数という概念を利用する。
 ==次数分布の母関数==
-一般の次数分布<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>p(k)</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>G_v(z) = \sum p(k) z^k</math>
+しかし、頂点''v''の隣にある頂点''w''の次数分布はもはや<math>p(k)</math>ではない。
+辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えよう。
+選ばれた辺の先には、他の点が等確率でくることはない。次数の大きい点のほうが、次数に比例して存在する確率が高くなるだろう。
+つまり、もう片側にある端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した<math>\textstyle kp(k)/\Sigma_j jp(j)</math>となる（分母は正規化定数）。
+よってある頂点''v''の隣にある頂点''w''の次数分布の母関数は
-相転移が起きるのは頂点から伸びていく辺の期待値が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>のときだけ、つまり行き止まりが極端に多くない限り、連結成分は繋がって無限に大きくなることを意味している。
+<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>
+母関数においては、次数<math>k</math>に対して<math>x^k</math>が対応する。
+頂点''v''の先に''w''がついているとき、''w''から''v''以外に伸びる辺数に注目しよう。
+その母関数は上の式を<math>x</math>で割ればよいから
+<math>G_w(x) = \frac{G'_v(x)}{G'_v(1)}</math>
+==占有される頂点の母関数==
+パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときである。
+ただし、このときの母関数はグラフ全体の次数分布を示す<math>G_v</math>ではなく、占有された頂点のみによる部分ネットワークの母関数である。
+したがって、母関数を区別して<math>F_v</math>と記そう。''F''と''G''の関係は、各頂点が確率''q''で占有されるため
+<math>
+\begin{align}
+F'_v(v) &= q G'_v(v) = q \langle k \rangle \\
+F''_v(v) &= q^2G''_v(v) = q^2 (\langle k^2 \rangle - \langle k \rangle)
+\end{align}
+</math>
+つまり''G''と''F''の次数平均と二乗平均をそれぞれ<math>\langle k \rangle</math>, <math>\langle l \rangle</math>と書くと
+<math>
+\begin{align}
+\langle l \rangle &= q \langle k \rangle \\
+\langle l^2 \rangle &= q^2 (\langle k^2 \rangle - \langle k \rangle) + q \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>\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>のときに発散する。有限のネットワークではその値も有限だが、大きな値になるために
+非常に低い値でパーコレートする。
 <!----
+別の書き方では<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 19: / Line 89: @@
 連結成分のサイズの期待値は<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

Revision as of 10:10, 3 June 2010

Contents

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

次数分布の母関数

占有される頂点の母関数

パーコレーション

ランダムグラフの場合

スケールフリーネットワークの場合

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox