Aritalab:Lecture/NetworkBiology/Percolation on Graph

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m (占有される頂点の母関数)
m (グラフ上のパーコレーション)
Line 4: Line 4:
  
 
グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。
 
グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。
この内容を読む前に[[Aritalab:Lecture/Basic/Generating Function|母関数の概念]]を復習しておいてください。
+
母関数の説明を理解するには、[[Aritalab:Lecture/Basic/Generating Function|母関数の概念]]を復習しておいてください。
 +
 
 +
ただ、面倒な説明を使わなくても言っていることは以下のとおりです。あるネットワークの平均次数が <k> で与えられるとき、隣接点の平均次数は (<k<sup>2</sup>> - <k>) / <k> になります。この本数の枝のうち、確率 q でサイトが ON になる場合、隣接点の周りで占有される頂点数は q (<k<sup>2</sup>> - <k>) / <k> になります。これが 1 を上回る場合は臨界になるので、1 = q (<k<sup>2</sup>> - <k>) / <k> を解いて、q<sub>c</sub> = 1 / (<k<sup>2</sup>> / <k>) - 1 が得られます。つまり、<k<sup>2</sup>> / <k> のバランスに臨界確率が左右されるということです。
  
 
==次数分布の母関数==
 
==次数分布の母関数==

Revision as of 15:47, 3 August 2016

Wiki Top Up one level レポートの書き方 Arita Laboratory

Contents

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

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

ただ、面倒な説明を使わなくても言っていることは以下のとおりです。あるネットワークの平均次数が <k> で与えられるとき、隣接点の平均次数は (<k2> - <k>) / <k> になります。この本数の枝のうち、確率 q でサイトが ON になる場合、隣接点の周りで占有される頂点数は q (<k2> - <k>) / <k> になります。これが 1 を上回る場合は臨界になるので、1 = q (<k2> - <k>) / <k> を解いて、qc = 1 / (<k2> / <k>) - 1 が得られます。つまり、<k2> / <k> のバランスに臨界確率が左右されるということです。

次数分布の母関数

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

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

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

辺をランダムに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 に近づきます。


Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox