次数・道・連結成分｜ネットワーク科学

← ネットワーク科学一覧

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：グラフの表現　|　関連：グラフの走査・次数中心性と次数分布

要点（BLUF）

次数 $\deg(v)$ はノードに接続するエッジ数。局所的な「つながりの多さ」を測る最も基本の量。
道（パス） は同じノードを通らずに $u$ から $v$ へ至る経路。最短路の長さがノード間の「距離」。
連結成分 は互いに到達可能なノードの極大集合。大域的な「まとまり」を捉える。

概念：局所→経路→大域

グラフを手にしたら、まず3つの量を測ります。ノード1個の局所量（次数）、2点間の経路（道）、グラフ全体のまとまり（連結成分）。この3段階で、ミクロからマクロまでの骨格がつかめます。

数式による定義

次数：無向グラフでノード $v$ の次数は、 $v$ に接続するエッジの本数。隣接行列を使えば行の和です。

\deg(v) = \sum_{u \in V} A_{vu}

有向グラフでは入次数 $\deg^{-}(v)$ （入ってくる矢印）と出次数 $\deg^{+}(v)$ （出ていく矢印）に分かれます。

握手補題（handshaking lemma）：すべてのノードの次数を足すと、エッジ数のちょうど2倍になります。

\sum_{v \in V} \deg(v) = 2m

各エッジが両端で1ずつ次数に寄与するからです。系として「次数が奇数のノードは偶数個ある」が従います。

道：ノード列 $v_0, v_1, \dots, v_k$ で、連続する各対 $(v_{i},v_{i+1})$ がエッジであり、ノードがすべて相異なるもの。長さは辺の数 $k$ 。最短の道の長さ $d(u,v)$ を距離と呼びます。

連結成分：「 $u$ から $v$ へ道がある」という関係は同値関係になり、その同値類が連結成分です。グラフ全体が1つの成分なら連結といいます。

直観

次数は「友達の数」、距離は「何人を介して知り合えるか」、連結成分は「同じ交友圏に属するグループ」。連結成分が複数あるグラフは、互いに行き来できない島の集まりだと思えばよいです。

コードで確認

import networkx as nx

# 3ノードの三角形 + 別の辺 + 孤立ノード
G = nx.Graph()
G.add_edges_from([(0,1),(1,2),(0,2),(3,4)])
G.add_node(5)  # 孤立ノード

print("各ノードの次数:", dict(G.degree()))
print("連結成分の数 =", nx.number_connected_components(G))
print("成分（ノード集合）:", [sorted(c) for c in nx.connected_components(G)])

comp = G.subgraph([0,1,2])
print("0→2 の最短路:", nx.shortest_path(comp, 0, 2))

deg_sum = sum(dict(G.degree()).values())
print("握手補題チェック: 次数和 =", deg_sum, " = 2 * エッジ数", 2*G.number_of_edges())

実行結果：

各ノードの次数: {0: 2, 1: 2, 2: 2, 3: 1, 4: 1, 5: 0}
連結成分の数 = 3
成分（ノード集合）: [[0, 1, 2], [3, 4], [5]]
0→2 の最短路: [0, 2]
握手補題チェック: 次数和 = 8  = 2 * エッジ数 8

次数和 8 がエッジ数 4 のちょうど2倍になっていること（握手補題）を確認してください。グラフは3つの島（三角形・1本の辺・孤立点）に分かれています。

数式の直観的意味

握手補題 $\sum_v \deg(v) = 2m$ は、いわば「握手の総数を2通りで数える」議論です。1回の握手（エッジ）には2本の手（端点）が関わるので、手の総数（次数和）は握手の数の2倍。当たり前に見えて、次数分布から平均次数 $\langle k \rangle = 2m/n$ を導く基礎になります（次数中心性と次数分布）。

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

道（path）と歩道（walk）の混同：歩道は同じノードを通ってよい、道は通らない。 $A^k$ が数えるのは歩道です。
距離が無限のことがある：別の連結成分にあるノード間の距離は未定義（または $\infty$ ）。平均路長を計算するときは最大連結成分に限るのが通例（距離・直径・平均路長）。
孤立ノードを忘れる：次数0のノードも立派なノード。連結成分数やノード数の数え方に影響します。

対応シミュレーション

本文のコードがそのまま検証用です。