Aritalab:Lecture/NetworkBiology/Watts-Strogatz Model

Wiki Top

Up one level

レポートの書き方

Arita Laboratory

スモールワールド

ディズニーランドに It's a Small World というアトラクションがあります。友達という概念をネットワークで表現すると、世間の狭さは平均頂点間距離 L が小さいことに相当します。現実のネットワークは平均頂点間距離 L およびクラスター係数 C が大きい ( L = O(log N), C = 0.2 ∼ 0.3 ) ことが特徴です。

ランダムグラフ (Erdos-Renyi Model) は L が小さいものの、C が大きくなりません。 逆に格子グラフは L も C も大きくなります。これら二つのグラフの特徴を併せ持つモデルを Watts と Strogatz が提唱して一大ブームになりました。

歴史と参考図書

• 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頂点間の辺が張りなおしを防げばよいので $C(p) = C(0)(1-p)^3$。