Aritalab:Lecture/NetworkBiology/Percolation on Graph

Revision as of 10:35, 28 August 2015

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

グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。この内容を読む前に母関数の概念を復習しておいてください。

次数分布の母関数

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

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

になります。しかし、頂点 v の隣にある頂点 w の次数分布はもはや $p(k)$ ではありません。選ばれた辺の先には、他の点が等確率でくることはないからです。例えば、スケールフリーネットワークの中からランダムに１つ頂点を選ぶと次数の少ないものが選ばれますが、そこから辺を１つたどった先はハブ頂点につながる確率が高くなります。つまり、次数が大きいほうが、（次数に比例して）存在する確率が高くなります。

辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えましょう。もう片側の端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した値になります（分母は正規化定数）。

$\frac{kp(k)}{\sum_j jp(j)}$

よってある頂点 v の隣にくる頂点 w の次数分布の母関数は以下のとおりです。

$\sum_{k=0}^{\infty}x^k\frac{kp(k)}{\sum_jjp(j)} = x\frac{\sum_k kx^{(k-1)}p(k)}{\sum_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$ と記しましょう。また G の平均次数を $\langle k \rangle$ とします。平均次数を母関数を用いて表現すると、占有された頂点のみの平均次数がわかります　(式の導出は確率母関数のページを参照）。

$\begin{align} F'_v(1) &= q G'_v(1) = q \langle k \rangle \end{align}$

相転移が起きるのは $F_w'(1) = 1$ のときです。

$\begin{align} F'_w(1) &= q G'_w(1) = q \Big(\frac{G'_v(x)}{G'_v(1)}\Big)' \Big|_{x=1} = q \frac{G''_v(1)}{G'_v(1)} \end{align}$

$G''_v(1) = \langle k^2 \rangle - \langle k \rangle, G'_v(1) = \langle k \rangle$ を代入すると $q_c = \frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle} - 1}$

すなわち、 $\langle k^2 \rangle$ が大きく $\langle k \rangle$ を上回るときに　 $q_c$ は小さくなります。ハブの k は大きくなりますから、 $k^2$ は更に大きくなります。次数の大きなハブがあるほど、パーコレーションが起きやすいということです。また全ての次数が同じとき、 $\langle k^2 \rangle = \langle k \rangle^2$ となりベーテ格子の結果と一致します。

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

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

ランダムグラフの場合

次数の分布がポアソン分布になるランダムグラフをかんがえましょう。平均と分散は等しく　 $E[k] = V[k] = \langle k \rangle$ になります。このとき $\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle$ になるので

$q_c = 1 / \langle k \rangle$

すなわち、平均次数に反比例して浸透確率が下がっていきます。

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

次数の分布が、べき分布 $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 33: / Line 33: @@
 パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が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>F_v</math> と記しましょう。また ''G'' の平均次数を <math>\langle k \rangle</math> とします。平均次数を母関数を用いて表現すると、占有された頂点のみの平均次数がわかります
-と書くと
+　(式の導出は[[Aritalab:Lecture/Basic/Probability_Generating_Function|確率母関数のページ]]を参照）。
-<math>
-\begin{align}
-\langle l \rangle &= q \langle k \rangle \\
-\end{align}
-</math>
-です。
-この関係から　(式の導出は[[Aritalab:Lecture/Basic/Probability_Generating_Function|確率母関数のページ]]を参照）
 <math>

Aritalab:Lecture/NetworkBiology/Percolation on Graph

Revision as of 10:35, 28 August 2015

Contents

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

次数分布の母関数

占有される頂点の母関数

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

ランダムグラフの場合

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

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox