Aritalab:Lecture/NetworkBiology/Percolation on Graph
From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
m (→パーコレーションの起こりやすさ) |
m |
||
Line 3: | Line 3: | ||
==グラフ上のパーコレーション== | ==グラフ上のパーコレーション== | ||
− | + | グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。ここでの議論は[[Aritalab:Lecture/Basic/GF_DegreeDistribution|母関数を使った説明]]もあります。 | |
− | + | ||
− | + | あるネットワークの平均次数が <k> で与えられるとき、隣接点の平均次数は <math>\textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}</math> になります。この本数のうち、確率 q でサイトが ON になる場合、隣接点の周りで占有される頂点数は <math>q \textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}</math> になります。これが 1 を上回る場合に相転移をおこすので、臨界確率 <math>q_c = \textstyle \frac{1}{\langle k^2 \rangle / \langle k \rangle - 1 }</math> が得られます。つまり、<k<sup>2</sup>> / <k> のバランスに臨界確率が左右されるということです。 | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | </math> | + | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | <math> | + | |
− | q_c = \frac{1} | + | |
− | </math> | + | |
− | + | ||
− | + | ||
− | + | ||
==パーコレーションの起こりやすさ== | ==パーコレーションの起こりやすさ== | ||
− | いかなる次数分布でも、<math>\langle k^2 \rangle</math>が<math>\langle k \rangle</math> | + | いかなる次数分布でも、<math>\langle k^2 \rangle</math>が<math>\langle k \rangle</math>に比して大きいと、低い浸透確率で相転移が起こります。 |
===格子グラフ、Erdosブラフ=== | ===格子グラフ、Erdosブラフ=== |
Latest revision as of 12:19, 6 August 2016
Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
[edit] グラフ上のパーコレーション
グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。ここでの議論は母関数を使った説明もあります。
あるネットワークの平均次数が <k> で与えられるとき、隣接点の平均次数は になります。この本数のうち、確率 q でサイトが ON になる場合、隣接点の周りで占有される頂点数は になります。これが 1 を上回る場合に相転移をおこすので、臨界確率 が得られます。つまり、<k2> / <k> のバランスに臨界確率が左右されるということです。
[edit] パーコレーションの起こりやすさ
いかなる次数分布でも、がに比して大きいと、低い浸透確率で相転移が起こります。
[edit] 格子グラフ、Erdosブラフ
次数が一定の場合、 です。すなわち、 となります。
次数分布がポアソン分布をなす場合、平均と分散は等しく になります。 このとき です。この場合も格子グラフとほぼ同じで、平均次数に反比例して浸透確率が下がります。
[edit] スケールフリーネットワーク
次数の分布が、べき分布 のときをかんがえましょう。 ここで はリーマンゼータ関数とします。
この値はのときに発散します。また が大きくなると の項が大きな要素を占めるのでほとんど 1 に近づきます。