距離・直径・平均路長｜ネットワーク科学

🎓 レベル：標準　|　重要度：B（推奨）

📎 前提：次数・道・連結成分・近接中心性・媒介中心性　|　関連：スモールワールド（Watts–Strogatz）

要点（BLUF）

距離 $d(u,v)$ は最短路のホップ数。これを集約すると、ネットワーク全体の「広がり」が見える。
直径はいちばん離れたペアの距離、平均路長 は全ペアの距離の平均、半径は最も中心的なノードの離心率。
多くの実ネットワークは巨大でも平均路長が小さい（六次の隔たり）。スモールワールド性の核。

概念：このネットワークはどれくらい広いか

中心性は「個々のノードの重要度」でしたが、ネットワーク全体の形も知りたい。「端から端まで何ホップか」「平均すると誰と誰は何人を介すか」。これを測るのが距離ベースの大域指標で、スモールワールド現象（スモールワールド（Watts–Strogatz））を定量化する土台です。

数式による定義

ノード $v$ の離心率（eccentricity） $\varepsilon(v)$ は、 $v$ から最も遠いノードまでの距離。

\varepsilon(v) = \max_{u} d(v,u)

これを使って3つの大域量が定義されます。

\text{直径} = \max_v \varepsilon(v), \qquad \text{半径} = \min_v \varepsilon(v)

\text{平均路長} = \frac{1}{n(n-1)} \sum_{u \neq v} d(u,v)

直径：最も離れた2ノードの距離。ネットワークの「最大の隔たり」。
半径：離心率が最小のノード（中心）の値。
平均路長：典型的な2点間の隔たり。スモールワールドかどうかの主役。

コードで確認

import networkx as nx

G = nx.karate_club_graph()
print("直径:", nx.diameter(G))
print("半径:", nx.radius(G))
print("平均最短路長:", round(nx.average_shortest_path_length(G), 4))

実行結果：

直径: 5
半径: 3
平均最短路長: 2.4082

34人のネットワークで、最も離れた2人でもわずか5ホップ、平均は約2.4ホップ。「世間は狭い」を数値が裏づけています。一般に実ネットワークでは、ノード数 $n$ が増えても平均路長は $\log n$ 程度にしか伸びません（スモールワールド性）。

数式の直観的意味

直径は「最悪ケースの隔たり」、平均路長は「典型的な隔たり」、半径は「最も恵まれた起点からの最悪ケース」。同じ距離行列を、最大で集約するか平均で集約するかの違いです。実ネットワークで平均路長が小さいのは、少数のハブやランダムな遠距離リンクが「近道」になるから。 $n$ 人を直線に並べれば平均路長は $n/3$ 程度ですが、ランダムなショートカットが入ると一気に $\log n$ まで縮みます（スモールワールド（Watts–Strogatz））。

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

非連結グラフでは直径・平均路長が無限：到達できないペアの距離は $\infty$ 。最大連結成分に限って計算するのが通例です。
直径だけ見ると外れ値に振り回される：たった1本のしっぽが直径を大きくする。全体像は平均路長や分布で見ること。
計算コスト：全ペア最短路は $O(nm)$ （BFS を全点から）。大規模ネットワークではサンプリング近似を使います。

対応シミュレーション

本文のコードがそのまま検証用です。 $\log n$ スケーリングの実験はスモールワールド（Watts–Strogatz）。