Aritalab:Lecture/NetworkBiology/Percolation on Graph

From Metabolomics.JP
Jump to: navigation, search
Wiki Top Up one level レポートの書き方 Arita Laboratory

Contents

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

グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。ここでの議論は母関数を使った説明もあります。

あるネットワークの平均次数が <k> で与えられるとき、隣接点の平均次数は \textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle} になります。この本数のうち、確率 q でサイトが ON になる場合、隣接点の周りで占有される頂点数は q \textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle} になります。これが 1 を上回る場合に相転移をおこすので、臨界確率 q_c = \textstyle \frac{1}{\langle k^2 \rangle / \langle k \rangle - 1 } が得られます。つまり、<k2> / <k> のバランスに臨界確率が左右されるということです。

パーコレーションの起こりやすさ

いかなる次数分布でも、\langle k^2 \rangle\langle k \rangleに比して大きいと、低い浸透確率で相転移が起こります。

格子グラフ、Erdosブラフ

次数が一定の場合、\langle k^2 \rangle = \langle k \rangle^2 です。すなわち、q_c = 1 / \langle k \rangle となります。

次数分布がポアソン分布をなす場合、平均と分散は等しく E[k] = V[k] = \langle k \rangle になります。 このとき \langle k^2 \rangle = \langle k \rangle^2 + \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