グラフラプラシアンとスペクトル

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：グラフの表現・ランダムウォークと拡散の数理　|　関連：スペクトルクラスタリング

要点（BLUF）

グラフラプラシアン $L = D - A$ （次数行列 − 隣接行列）。グラフの「微分作用素」にあたる対称半正定値行列。
固有値0の重複度が連結成分の数に一致。第2固有値 $\lambda_2$ （代数的連結度）が「どれだけ繋がっているか」を測る。
固有値分解（統計の土台）を通じて、コミュニティ・拡散・同期などの大域構造が露わになる。

概念：グラフを行列の固有値で読む

隣接行列（グラフの表現）はグラフの全情報を持ちますが、その固有値・固有ベクトルを調べると、目で見ても分からない大域構造が浮かび上がります。中でもグラフラプラシアンは、連結性・コミュニティ・拡散・同期を統一的に語る中心的な行列です。固有値分解そのものは統計・線形代数のturf — ここではグラフ特有の意味に集中します。

数式による定義

次数を対角に並べた $D = \mathrm{diag}(\deg(v))$ と隣接行列 $A$ から、

L = D - A

成分で書くと $L_{ii} = \deg(i)$ 、 $L_{ij} = -1$ （エッジあり）、 $0$ （なし）。 $L$ は対称で半正定値（固有値はすべて $\geq 0$ ）。その理由は2次形式が

\mathbf{x}^\top L \mathbf{x} = \sum_{(i,j)\in E} (x_i - x_j)^2 \geq 0

と、隣接ノードの値の差の2乗和になるから。これは「 $L$ がグラフ上の微分（差分）作用素」であることを意味します。

スペクトルが符号化する大域構造

ラプラシアンの固有値を $0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ と並べると：

$\lambda_1 = 0$ は常に成り立つ（全成分等しいベクトルが固有ベクトル）。
固有値0の重複度＝連結成分の数。グラフが $c$ 個の島なら0が $c$ 個。
$\lambda_2 > 0$ ⟺ グラフが連結。 $\lambda_2$ を**代数的連結度（Fiedler値）**と呼び、大きいほど密に繋がり、切り離しにくい。

コードで確認

import networkx as nx
import numpy as np

def clean(arr):
    return [0.0 if abs(x) < 1e-9 else round(float(x), 3) for x in arr]  # 数値誤差の-0を0に

# 連結なサイクル C6
G = nx.cycle_graph(6)
eig = np.sort(np.linalg.eigvalsh(nx.laplacian_matrix(G).toarray().astype(float)))
print("C6 のラプラシアン固有値      :", clean(eig))
print("  ゼロ固有値の数(=連結成分数):", int(np.sum(np.isclose(eig, 0))))

# 非連結：2つの三角形
G2 = nx.disjoint_union(nx.complete_graph(3), nx.complete_graph(3))
eig2 = np.sort(np.linalg.eigvalsh(nx.laplacian_matrix(G2).toarray().astype(float)))
print("2つの三角形の固有値          :", clean(eig2))
print("  ゼロ固有値の数(=連結成分数):", int(np.sum(np.isclose(eig2, 0))))

print("P6 の代数的連結度(λ2)        :", round(float(nx.algebraic_connectivity(nx.path_graph(6))), 4))

実行結果：

C6 のラプラシアン固有値      : [0.0, 1.0, 1.0, 3.0, 3.0, 4.0]
  ゼロ固有値の数(=連結成分数): 1
2つの三角形の固有値          : [0.0, 0.0, 3.0, 3.0, 3.0, 3.0]
  ゼロ固有値の数(=連結成分数): 2
P6 の代数的連結度(λ2)        : 0.2679

連結なサイクル C6 は0固有値が1個（連結成分1つ）。2つの三角形を離して置くと0固有値が2個になり、連結成分の数とぴったり一致します。一直線のパス P6 の代数的連結度は0.27と小さい — 細長くて切れやすい構造を反映しています。

数式の直観的意味

$\mathbf{x}^\top L\mathbf{x} = \sum_{(i,j)} (x_i-x_j)^2$ は「隣り合うノードに似た値を割り当てたときの滑らかさ」を測ります。固有値が小さい固有ベクトルは「エッジの両端で値が似ている＝なめらか」なベクトル。0固有値のベクトルは「各連結成分内で完全に一定」 — だから0の数が成分数になる。 $\lambda_2$ の固有ベクトル（Fiedlerベクトル）は「全体を最もなめらかに2つに分ける軸」で、これがコミュニティ分割（スペクトルクラスタリング）の出発点です。ラプラシアンはランダムウォーク（ランダムウォークと拡散の数理）の生成作用素でもあり、拡散の速さも $\lambda_2$ が支配します。

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

ラプラシアンには複数の流儀： $L=D-A$ （組合せ）、 $L_{sym}=D^{-1/2}LD^{-1/2}$ （対称正規化）、 $L_{rw}=D^{-1}L$ （ランダムウォーク）。用途で使い分け、固有値の範囲も変わります。
「スペクトル」はラプラシアン固有値の集合：隣接行列のスペクトルとは別。文脈でどちらか確認を。
代数的連結度 ≠ 連結成分数：前者は連結度合いの強さ（連続値）、後者は島の個数（整数）。混同しないこと。

対応シミュレーション

本文のコードがそのまま検証用です。Fiedlerベクトルによる分割はスペクトルクラスタリング。