Aritalab:Lecture/NetworkBiology/Percolation on Graph

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology
Revision as of 13:35, 2 June 2010 by Adm (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Contents

ランダムグラフでのパーコレーション

ランダムグラフは、ある次数分布に従うツリーとみなすことができる。 これを扱うには、母関数という概念を利用する。

母関数

ある分布p(k)の母関数(generating function)を\textstyle G_0(x) = \Sigma_{k=0}^{\infty}p(k)x^kと定義する。確率p(k)は全部足すと1なので、\textstyle G_0(1) = \Sigma_{k=0}^{\infty}p(1)1^k = 1が成立する。また\textstyle G_0'(1) = \Sigma_{k=0}^{\infty}p(k)kx^{(k-1)} \bigg|_{x=1} = \Sigma kp(k) = \langle k \rangle\textstyle G_0''(1) = \Sigma_{k=0}^{\infty}p(k)k(k-1)x^{(k-2)} \bigg|_{x=1} = \Sigma k(k-1)p(k) = \langle k^2 \rangle - \langle k \rangleとなる。

次数分布の母関数

一般の次数分布p(k)の母関数は上で述べたG_v(x)になる。ある頂点vの隣にある頂点wの次数分布はもはやp(k)ではなく、母関数も異なる。辺をランダムに1本選んだとき、もう片方にある端点がどんな次数になっているかをあらわす分布が必要である。辺をランダムに選んだ先には、次数が大きい点が存在する確率が高い。つまり、もう片側にある端点の次数がkになる確率は、辺の数で重みをつけた次数分布に比例して\textstyle kp(k)/\Sigma_j jp(j)となる(分母は正規化定数)。よってある頂点vの隣にある頂点wの次数分布の母関数は\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)}となる。

母関数においては、次数kに対してx^kが対応することに注意しよう。頂点vの先にwがついているとき、wが持つ辺の一つはvに戻るため、外側に伸びる辺はk-1になる。そのときの母関数は上の式をxで割ればよくG_e(x) = \frac{G'_v(x)}{G'_v(1)}と書ける。


相転移が起きるのは頂点から伸びていく辺の期待値が1をちょうど超えるとき、つまりG_e'(1) = \frac{G'_v(1)}{G'_v(1)} = 1のとき。すなわち\langle k^2 \rangle = 2 \langle k \rangleのときになる。別の書き方では\Sigma k(k-2)p(k) = 0だが、この和のうち負の値になるのはk=1のときだけ、つまり行き止まりが極端に多くない限り、連結成分は繋がって無限に大きくなることを意味している。


パーコレーション

パーコレーションにおいては、確率(1-q)で辺が繋がらなくなる。実効的な次数が\bar{k}になる確率は\bar{p}(\bar{k}) = \Sigma_{k=\bar{k}}^{\infty}p(k) \tbinom{k}{\bar{k}}q^{\bar{k}}(1-q)^{k-\bar{k}}である。


大雑把に言うと相転移を起こすのは\langle k^2 \rangle q^2= 2 \langle k \rangle qのとき、つまりq = 2 \langle k \rangle / \langle k^2 \rangleのあたりである。\langle k^2 \rangleが大きいと非常に低いパーコレーション確率でも相転移が起こる。つまり感染率が低くてもネットワーク全体に蔓延する。この値はべき分布p(k)=ck^{-\gamma}のときおよそ\Sigma_kk^2p(k) = c\Sigma k^{2-\gamma}になるため、\gammaが3以下であればパーコレートする。

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox