Aritalab:Lecture/NetworkBiology/Percolation on Graph
m |
|||
Line 19: | Line 19: | ||
母関数においては、次数<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>で割ればよい。 | |
<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 27: | ||
パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときである。 | パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときである。 | ||
ただし、このときの母関数はグラフ全体の次数分布を示す<math>G_v</math>ではなく、占有された頂点のみによる部分ネットワークの母関数である。 | ただし、このときの母関数はグラフ全体の次数分布を示す<math>G_v</math>ではなく、占有された頂点のみによる部分ネットワークの母関数である。 | ||
− | したがって、母関数を区別して<math>F_v</math>と記そう。''F''と''G''の関係は、各頂点が確率''q''で占有されるため | + | したがって、母関数を区別して<math>F_v</math>と記そう。''F''と''G''の関係は、各頂点が確率''q''で占有されるため''G''と''F''の次数平均をそれぞれ<math>\langle k \rangle</math>, <math>\langle l \rangle</math> |
− | + | と書くと | |
<math> | <math> | ||
\begin{align} | \begin{align} | ||
− | + | \langle l \rangle &= q \langle k \rangle \\ | |
− | + | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
− | + | この関係から | |
<math> | <math> | ||
\begin{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} | \end{align} | ||
</math> | </math> | ||
Line 51: | Line 50: | ||
</math> | </math> | ||
− | + | 代入すると | |
<math> | <math> | ||
q_c = \frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle} - 1} | q_c = \frac{1}{\frac{\langle k^2 \rangle}{\langle k \rangle} - 1} | ||
</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>\langle k^2 \rangle</math>が<math>\langle k \rangle</math>に比して大きいと、低いパーコレーション確率で相転移が起こることを見た。 |
===ランダムグラフの場合=== | ===ランダムグラフの場合=== |
Revision as of 15:17, 5 June 2010
Contents |
グラフ上のパーコレーション
グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみよう。 ここでは母関数という概念を利用する。
次数分布の母関数
グラフの次数分布を与えられたとき、その母関数は
しかし、頂点vの隣にある頂点wの次数分布はもはやではない。 辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えよう。 選ばれた辺の先には、他の点が等確率でくることはない。次数の大きい点のほうが、次数に比例して存在する確率が高くなるだろう。 つまり、もう片側にある端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化したとなる(分母は正規化定数)。 よってある頂点vの隣にある頂点wの次数分布の母関数は
母関数においては、次数に対してが対応する。 頂点vの先にwがついているとき、wからv以外に伸びる辺数に注目しよう。 vからwへの辺1本を除いた、wに関する母関数は上の式をで割ればよい。
占有される頂点の母関数
パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときである。 ただし、このときの母関数はグラフ全体の次数分布を示すではなく、占有された頂点のみによる部分ネットワークの母関数である。 したがって、母関数を区別してと記そう。FとGの関係は、各頂点が確率qで占有されるためGとFの次数平均をそれぞれ, と書くと
この関係から
相転移が起きるのはのときだから
代入すると
すなわち、が大きくを上回るとき、は小さくなる。
パーコレーション
いかなる次数分布でも、がに比して大きいと、低いパーコレーション確率で相転移が起こることを見た。
ランダムグラフの場合
ランダムグラフの場合は次数分布がポアソン分布になる。このときになるので
すなわち、平均次数が大きくなるほどパーコレートしやすくなる。
スケールフリーネットワークの場合
べき分布のとき
この値はFailed to parse (lexing error): \gamma \leq 3 のときに発散する。有限のネットワークではその値も有限だが、大きな値になるために 非常に低い値でパーコレートする。