Aritalab:Lecture/NetworkBiology/Percolation on Graph

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

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

あるネットワークの平均次数が <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 }$ が得られます。つまり、<k²> / <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)}$