Aritalab:Lecture/NetworkBiology/Percolation on Graph

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m (→‎パーコレーション)
m
Line 3: Line 3:
 
==グラフ上のパーコレーション==
 
==グラフ上のパーコレーション==
  
−
グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみよう。
+
グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。
−
ここでは母関数という概念を利用する。
+
この内容を読む前に[[Aritalab:Lecture/Basic/Generating Function|母関数の概念]]を復習しておいてください。
  
 
==次数分布の母関数==
 
==次数分布の母関数==
−
グラフの次数分布<math>p(k)</math>を与えられたとき、その母関数は
+
グラフの次数分布 <math>p(k)</math> を与えられたとき、その母関数は
  
−
<math>G_v(z) = \sum p(k) z^k</math>
+
<math>G_v(x) = \sum p(k) x^k</math>
  
−
しかし、頂点''v''の隣にある頂点''w''の次数分布はもはや<math>p(k)</math>ではない。
+
になります。しかし、頂点 ''v'' の隣にある頂点 ''w'' の次数分布はもはや <math>p(k)</math> ではありません。
−
辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えよう。
+
選ばれた辺の先には、他の点が等確率でくることはないからです。
−
選ばれた辺の先には、他の点が等確率でくることはない。次数の大きい点のほうが、次数に比例して存在する確率が高くなるだろう。
+
辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えましょう。
−
つまり、もう片側にある端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した<math>\textstyle kp(k)/\Sigma_j jp(j)</math>となる（分母は正規化定数）。
+
次数の大きい点のほうが、次数に比例して存在する確率が高くなります。
−
よってある頂点''v''の隣にある頂点''w''の次数分布の母関数は
+
つまり、もう片側にある端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した<math>\textstyle kp(k)/\Sigma_j jp(j)</math>となります（分母は正規化定数）。
 +
よってある頂点 ''v'' の隣にくる頂点 ''w'' の次数分布の母関数は
  
 
<math>\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)}</math>
 
<math>\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)}</math>
  
−
母関数においては、次数<math>k</math>に対して<math>x^k</math>が対応する。
+
母関数においては、次数 <math>k</math> に対して <math>x^k</math> が対応します。
−
頂点''v''の先に''w''がついているとき、''w''から''v''以外に伸びる辺数に注目しよう。
+
頂点 ''v'' の先に ''w'' がついているとき、''w'' から ''v'' 以外に伸びる辺数に注目します。
−
''v''から''w''への辺1本を除いた、''w''に関する母関数は上の式を<math>x</math>で割ればよい。
+
''v'' から ''w'' への辺1本を除いた、''w'' に関する母関数は上の式を<math>x</math>で割ったものにあたります。
  
 
<math>G_w(x) = \frac{G'_v(x)}{G'_v(1)}</math>
 
<math>G_w(x) = \frac{G'_v(x)}{G'_v(1)}</math>
Line 27: Line 28:
 
==占有される頂点の母関数==
 
==占有される頂点の母関数==
  
−
パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときである。
+
パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときです。
−
ただし、このときの母関数はグラフ全体の次数分布を示す<math>G_v</math>ではなく、占有された頂点のみによる部分ネットワークの母関数である。
+
ただし、このときの母関数はグラフ全体の次数分布を示す <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> と記しましょう。関数 ''F'' と ''G'' の関係は、各頂点が確率 ''q'' で占有されるため ''G'' と ''F'' の次数平均をそれぞれ<math>\langle k \rangle</math>, <math>\langle l \rangle</math>
 
と書くと
 
と書くと
 
<math>
 
<math>
Line 58: Line 59:
 
</math>
 
</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>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>に比して大きいと、低い浸透確率で相転移が起こることをみてきました。
  
 
===ランダムグラフの場合===
 
===ランダムグラフの場合===
  
−
ランダムグラフの場合は次数分布がポアソン分布になる。このとき<math>\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle </math>になるので
+
ランダムグラフの場合は次数分布がポアソン分布になります。
 +
このとき<math>\langle k^2 \rangle = \langle k \rangle^2 + \langle k \rangle </math>になるので
  
 
<math>q_c = 1 / \langle k \rangle</math>
 
<math>q_c = 1 / \langle k \rangle</math>
  
−
すなわち、平均次数が大きくなるほど浸透しやすくなる。
+
すなわち、平均次数が大きくなるほど浸透しやすくなります。
  
 
===スケールフリーネットワークの場合===
 
===スケールフリーネットワークの場合===
Line 80: Line 82:
 
</math>
 
</math>
  
−
この値は<math>\gamma　\leq 3</math>のときに発散する。有限のネットワークではその値も有限だが、大きな値になるために非常に低い値で浸透すると考えてよい。
+
この値は<math>\gamma　\leq 3</math>のときに発散します。有限のネットワークではその値も有限ですが、大きな値になるために非常に低い値で浸透すると考えてよさそうです。
  
 
<!----
 
<!----

Revision as of 17:29, 15 June 2011

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

Contents

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

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

次数分布の母関数

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

G_v(x) = \sum p(k) x^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=255185"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox