Aritalab:Lecture/NetworkBiology/Percolation on Graph

Revision as of 15:17, 5 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以外に伸びる辺数に注目しよう。 vからwへの辺1本を除いた、wに関する母関数は上の式を $x$ で割ればよい。

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

占有される頂点の母関数

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

この関係から

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

相転移が起きるのは $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$ を上回るとき、 $q_c$ は小さくなる。

パーコレーション

いかなる次数分布でも、 $\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 19: / Line 19: @@
 母関数においては、次数<math>k</math>に対して<math>x^k</math>が対応する。
 頂点''v''の先に''w''がついているとき、''w''から''v''以外に伸びる辺数に注目しよう。
-その母関数は上の式を<math>x</math>で割ればよいから
+''v''から''w''への辺1本を除いた、''w''に関する母関数は上の式を<math>x</math>で割ればよい。
 <math>G_w(x) = \frac{G'_v(x)}{G'_v(1)}</math>
@@ Line 27: / Line 27: @@
 パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときである。
 ただし、このときの母関数はグラフ全体の次数分布を示す<math>G_v</math>ではなく、占有された頂点のみによる部分ネットワークの母関数である。
-したがって、母関数を区別して<math>F_v</math>と記そう。''F''と''G''の関係は、各頂点が確率''q''で占有されるため
+したがって、母関数を区別して<math>F_v</math>と記そう。''F''と''G''の関係は、各頂点が確率''q''で占有されるため''G''と''F''の次数平均をそれぞれ<math>\langle k \rangle</math>, <math>\langle l \rangle</math>
+と書くと
 <math>
 \begin{align}
-F'_v(v) &= q G'_v(v) = q \langle k \rangle \\
+\langle l \rangle &= 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 \\
+F'_v(1) &= q G'_v(1) = q \langle k \rangle \\
-\langle l^2 \rangle &= q^2 (\langle k^2 \rangle - \langle k \rangle) + q \langle k \rangle
+F''_v(1) &= q^2G''_v(1) = q^2 (\langle k^2 \rangle - \langle k \rangle)
 \end{align}
 </math>
@@ Line 51: / Line 50: @@
 </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</math>が<math>\langle k \rangle</math>に比して大きいと、低いパーコレーション確率で相転移が起こることを見た。
 ===ランダムグラフの場合===

Aritalab:Lecture/NetworkBiology/Percolation on Graph

Revision as of 15:17, 5 June 2010

Contents

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

次数分布の母関数

占有される頂点の母関数

パーコレーション

ランダムグラフの場合

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

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox