Aritalab:Lecture/NetworkBiology/Watts-Strogatz Model

歴史と参考図書

• Watts DJ, Strogatz SH. "Collective dynamics of 'small-world' networks.". Nature 393 (6684):409–10, 1998. doi:10.1038/30918

Watts-Strogatz Model

各頂点が$k$個の隣接点に接続した環状の格子グラフにおいて（総辺数は$kn/2$）、確率$p$で辺を張り直したものをWatts-Strogatzモデルという。辺を張りなおすモデルは解析が難しいので、環状の格子グラフにポアソン過程として$pkn/2$本の辺を追加するモデルがよく使われる。

$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$。