Aritalab:Lecture/NetworkBiology/Percolation on Graph
From Metabolomics.JP
Contents |
ランダムグラフでのパーコレーション
ランダムグラフは、ある次数分布に従うツリーとみなすことができる。 これを扱うには、母関数という概念を利用する。
母関数
ある分布の母関数(generating function)をと定義する。確率は全部足すと1なので、が成立する。また、となる。
次数分布の母関数
一般の次数分布の母関数は上で述べたになる。ある頂点vの隣にある頂点wの次数分布はもはやではなく、母関数も異なる。辺をランダムに1本選んだとき、もう片方にある端点がどんな次数になっているかをあらわす分布が必要である。辺をランダムに選んだ先には、次数が大きい点が存在する確率が高い。つまり、もう片側にある端点の次数がになる確率は、辺の数で重みをつけた次数分布に比例してとなる(分母は正規化定数)。よってある頂点vの隣にある頂点wの次数分布の母関数はとなる。
母関数においては、次数に対してが対応することに注意しよう。頂点vの先にwがついているとき、wが持つ辺の一つはvに戻るため、外側に伸びる辺はになる。そのときの母関数は上の式をで割ればよくと書ける。
相転移が起きるのは頂点から伸びていく辺の期待値が1をちょうど超えるとき、つまりのとき。すなわちのときになる。別の書き方ではだが、この和のうち負の値になるのはのときだけ、つまり行き止まりが極端に多くない限り、連結成分は繋がって無限に大きくなることを意味している。
パーコレーション
パーコレーションにおいては、確率で辺が繋がらなくなる。実効的な次数がになる確率はである。
大雑把に言うと相転移を起こすのはのとき、つまりのあたりである。が大きいと非常に低いパーコレーション確率でも相転移が起こる。つまり感染率が低くてもネットワーク全体に蔓延する。この値はべき分布のときおよそになるため、が3以下であればパーコレートする。