Aritalab:Lecture/NetworkBiology/Percolation on Graph
m (→次数分布の母関数) |
m (→占有される頂点の母関数) |
||
Line 37: | Line 37: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
+ | です。 | ||
この関係から | この関係から |
Revision as of 19:26, 15 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 の次数平均をそれぞれ, と書くと です。
この関係から
相転移が起きるのはのときだから
代入すると
すなわち、が大きくを上回るとき、は小さくなります。
パーコレーション
いかなる次数分布でも、がに比して大きいと、低い浸透確率で相転移が起こることをみてきました。
ランダムグラフの場合
ランダムグラフの場合は次数分布がポアソン分布になります。 このときになるので
すなわち、平均次数が大きくなるほど浸透しやすくなります。
スケールフリーネットワークの場合
べき分布のとき
この値はFailed to parse (lexing error): \gamma \leq 3 のときに発散します。有限のネットワークではその値も有限ですが、大きな値になるために非常に低い値で浸透すると考えてよさそうです。