Aritalab:Lecture/NetworkBiology/Percolation on Graph

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m
m
Line 1: Line 1:
 +
{{Lecture/Header}}
 +
 
==グラフ上のパーコレーション==
 
==グラフ上のパーコレーション==
  

Revision as of 09:50, 10 June 2010

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

Contents

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

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

次数分布の母関数

グラフの次数分布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 のときに発散する。有限のネットワークではその値も有限だが、大きな値になるために 非常に低い値でパーコレートする。


Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/NetworkBiology/Percolation_on_Graph&oldid=255182"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox