Aritalab:Lecture/NetworkBiology/Watts-Strogatz Model

From Metabolomics.JP
Jump to: navigation, search
Wiki Top Up one level レポートの書き方 Arita Laboratory

Contents

歴史と参考図書

  • Watts DJ, Strogatz SH. "Collective dynamics of 'small-world' networks.". Nature 393 (6684):409–10, 1998. doi:10.1038/30918
  • Durrett R. "Random Graph Dynamics" Cambridge University Press, 2004.

Watts-Strogatz Model

各頂点がk個の隣接点に接続した環状の格子グラフにおいて(総辺数はkn/2)、確率pで辺を張り直したものをWatts-Strogatzモデルという。辺を張りなおすモデルは解析が難しいので、環状の格子グラフにポアソン過程としてpkn/2本の辺を追加するモデルがよく使われる。パラメータpを調節して格子とランダムグラフの中間状態を作成する点がポイント。

p=0のとき

クラスター係数

簡単のため左右の隣接点に同じ本数リンクを張ると仮定し、k = 2iとする。注目する点を原点とした-i \leq x, y < \leq iのxy座標系を考えたとき、|x - y| > iに対応する座標点は三角形K_3を形成せず、残りは形成する。その割合を考えるとC(0) = 3/4

平均頂点間距離

1ステップでk/2点スキップでき、環状格子で一番離れている点はn/2なので、L(0) \leq n / k

p=1のとき

ランダムグラフと思えばよい。

クラスター係数

k辺を張りかえるとき、n頂点の中からk隣接点を選べばよいのでC(1) \simeq k/n

平均頂点間距離

辺をランダムに張りかえるのでL(1) \simeq \log n / \log k

一般の場合

平均頂点間距離

導出は面倒だが以下の近似が知られている。\textstyle L(p)=\frac{n}{k}\frac{\log(2 pkn)}{4 pkn}

クラスター係数

簡単な近似では、K_3をなす3頂点間の辺が張りなおしを防げばよいので L(p) = L(0)(1-p)^3

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox