スモールワールド（Watts–Strogatz）

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：クラスタ係数と推移性・距離・直径・平均路長　|　関連：Erdős–Rényiランダムグラフ

要点（BLUF）

スモールワールド：高いクラスタ係数（近所は密）と短い平均路長（誰とでも数ホップ）を両立するネットワーク。
Watts–Strogatzモデル：規則的なリング格子のエッジを確率 $\beta$ で再配線する。 $\beta$ を上げると格子→ランダムへ連続変化。
ごく少数の「遠距離ショートカット」だけで平均路長が劇的に縮む — これが「世間は狭い」の正体。

概念：クラスタも近さも、両方ほしい

現実ネットワークには2つの一見矛盾する性質があります。①友達の友達は友達（高クラスタ、クラスタ係数と推移性）、②誰とでも数ホップで繋がる（短い平均路長、距離・直径・平均路長）。規則格子は①を満たすが距離が長い。ER（Erdős–Rényiランダムグラフ）は距離が短いがクラスタが低い。両方を同時に満たす仕組みを示したのが Watts–Strogatz モデルです。

モデルの定義

$n$ ノードをリング状に並べ、各ノードを両隣 $k/2$ 個ずつと繋ぐ（規則的リング格子、 $k$ -正則）。この段階ではクラスタ係数が高く、平均路長は $n/k$ 程度と長い。
各エッジを確率 $\beta$ で「再配線」する：片端をランダムな別ノードに繋ぎ替える。

$\beta$ が制御パラメータです。

\beta = 0 \;\Rightarrow\; \text{規則格子（高クラスタ・長距離）}

\beta = 1 \;\Rightarrow\; \text{ほぼランダムグラフ（低クラスタ・短距離）}

肝は中間領域（ $0 < \beta \ll 1$ ）。わずかな再配線が「遠距離ショートカット」を作り、平均路長を急落させる一方、再配線が少ないのでクラスタ係数はほぼ保たれます。

コードで確認

import networkx as nx

n, k = 500, 6
for beta in [0.0, 0.01, 0.1, 1.0]:
    G = nx.watts_strogatz_graph(n, k, beta, seed=1)
    L = nx.average_shortest_path_length(G)
    C = nx.average_clustering(G)
    print(f"β={beta}: 平均路長 L={L:.2f}, クラスタ係数 C={C:.3f}")

実行結果：

β=0.0: 平均路長 L=42.08, クラスタ係数 C=0.600
β=0.01: 平均路長 L=11.43, クラスタ係数 C=0.581
β=0.1: 平均路長 L=5.59, クラスタ係数 C=0.460
β=1.0: 平均路長 L=3.68, クラスタ係数 C=0.011

注目は $\beta=0.01$ ：エッジの1%を再配線しただけで平均路長が 42→11 とおよそ4分の1に激減、なのにクラスタ係数は $0.60→0.58$ とほぼ無傷。さらに $\beta=0.1$ でも $C=0.46$ を保ちつつ $L=5.6$ 。これがスモールワールド領域です。完全ランダム（ $\beta=1$ ）はクラスタ係数が $0.011$ まで崩れます。

相転移的な振る舞い

graph LR
    R["β=0<br/>規則格子<br/>高C・長L"] -->|"少し再配線"| S["0<β<<1<br/>スモールワールド<br/>高C・短L"]
    S -->|"再配線を増やす"| Rand["β=1<br/>ランダム<br/>低C・短L"]

平均路長 $L(\beta)$ は $\beta$ のごく初期で急落するのに対し、クラスタ係数 $C(\beta)$ はゆっくり減る。この減衰速度の差こそがスモールワールド領域を生みます。

数式の直観的意味

なぜ少数のショートカットで距離が激減するのか。規則格子では端から端まで「1ステップずつ歩く」しかなく $L \sim n/k$ 。だが遠距離リンクが1本あると、それが「ワープ装置」になって遠い領域を直結する。ショートカットが $\log n$ 本もあれば、ネットワーク全体が $L \sim \log n / \log k$ 程度まで縮みます。一方クラスタ係数は局所的な量なので、全体のごく一部を再配線しても影響が小さい。「大域（距離）は少数のリンクに敏感、局所（クラスタ）は鈍感」という非対称性が本質です。

⚠️ よくある誤解・落とし穴

スモールワールド＝スケールフリーではない：WS モデルの次数分布はほぼ一様（再配線で少し広がる程度）でハブは出ない。短距離＋高クラスタの話であって、べき則とは別の現象です（スケールフリー（Barabási–Albert））。
$\beta=1$ は ER に近いがクラスタが低すぎる：完全ランダム化は現実的でない。中間 $\beta$ が現実に近い。
平均路長が定義できるのは連結のとき：WS は通常連結ですが、 $\beta$ が大きいと稀に非連結になりえます。

対応シミュレーション

本文のコードがそのまま検証用です。次数の偏りを生む別モデルはスケールフリー（Barabási–Albert）。