Aritalab:Lecture/NetworkBiology/Percolation on Graph
m (→占有される頂点の母関数) |
m (→パーコレーション) |
||
Line 69: | Line 69: | ||
===ランダムグラフの場合=== | ===ランダムグラフの場合=== | ||
− | + | 次数の分布がポアソン分布になるランダムグラフをかんがえましょう。平均と分散は等しく <math>E[k] = V[k] = \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>になるので | ||
Line 78: | Line 78: | ||
===スケールフリーネットワークの場合=== | ===スケールフリーネットワークの場合=== | ||
− | + | 次数の分布が、べき分布 <math>p(k)=ck^{-\gamma}</math> のときをかんがえましょう。 | |
<math> | <math> |
Revision as of 03:42, 16 June 2011
Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
グラフ上のパーコレーション
グラフをある次数分布に従うツリーとみなすことで、パーコレーションを扱ってみます。 この内容を読む前に母関数の概念を復習しておいてください。
次数分布の母関数
グラフの次数分布 を与えられたとき、その母関数は
になります。しかし、頂点 v の隣にある頂点 w の次数分布はもはや ではありません。
選ばれた辺の先には、他の点が等確率でくることはないからです。
辺をランダムに1本選んだとき、もう片方にある端点がどんな次数分布をとるか考えましょう。
次数の大きい点のほうが、次数に比例して存在する確率が高くなります。
つまり、もう片側にある端点の次数分布は、最初の次数分布に辺の数で重みをつけてから正規化した
となります(分母は正規化定数)。
よってある頂点 v の隣にくる頂点 w の次数分布の母関数は
母関数においては、次数 に対して
が対応します。
頂点 v の先に w がついているとき、w から v 以外に伸びる辺数に注目しましょう。
v から w への辺1本ぶんを除いた w に関する母関数は、上の式を
で割ったものにあたります。
占有される頂点の母関数
パーコレーションで相転移が起きるのは、頂点から伸びていく辺の期待値が1をちょうど超えるときです。
ただし、このときの母関数はグラフ全体の次数分布を示す ではなく、占有された頂点のみによる部分ネットワークの母関数です。
したがって、母関数を区別して
と記しましょう。関数 F と G の関係は、各頂点が確率 q で占有されるため G と F の次数平均をそれぞれ
,
と書くと
です。
この関係から (式の導出は確率母関数のページを参照)
相転移が起きるのはのときだから
代入すると
すなわち、が大きく
を上回るときに
は小さくなります。
ハブの k は大きくなりますから、
は更に大きくなります。次数の大きなハブがあるほど、パーコレーションが起きやすいということです。
パーコレーション
いかなる次数分布でも、が
に比して大きいと、低い浸透確率で相転移が起こることをみてきました。
ランダムグラフの場合
次数の分布がポアソン分布になるランダムグラフをかんがえましょう。平均と分散は等しく になります。
このとき
になるので
すなわち、平均次数が大きくなるほど浸透しやすくなります。
スケールフリーネットワークの場合
次数の分布が、べき分布 のときをかんがえましょう。
この値はFailed to parse (lexing error): \gamma \leq 3 のときに発散します。有限のネットワークではその値も有限ですが、大きな値になるために非常に低い値で浸透すると考えてよさそうです。