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$個の隣接点に接続した環状の格子グラフにおいて、確率$p$で辺を張り直したものをWatts-Strogatzモデルという。

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