Spectral graph theory と Laplacian

中級編で 6B の固有値解析を扱いました。本章はそれを spectral graph theory として深掘りし、グラフ Laplacian と固有値スペクトルが集団の動学を決める枠組みを正式化します。

集合 → グラフ表現

集団の各メンバー $i = 1, \ldots, N$ を ノード、メンバー間の影響関係を エッジとするグラフ $G = (V, E)$ を構成します。エッジには重み $w_{ij}$(影響の強さ)を付ける。

中級編の結合行列 $A$ は 重み付き隣接行列($A_{ij} = w_{ij}$ for $(i,j) \in E$、0 otherwise)。

次数行列 D

ノード $i$ の 次数 $d_i = \sum_j w_{ij}$(自分に流れ込む全重みの和)。

対角行列 $D = \mathrm{diag}(d_1, \ldots, d_N)$。

グラフ Laplacian L

最も重要な行列が Laplacian:

$$ L = D - A $$

性質:

1. 対称(無向グラフなら)
2. 半正定値($L \succeq 0$)
3. 固有値 $0 = \lambda_1 \le \lambda_2 \le \cdots \le \lambda_N$
4. 最小固有値 0 に対応する固有ベクトルは 定数ベクトル $\mathbf{1} = (1,\ldots,1)^\top$

連結成分と Fiedler 値

$\lambda_1 = 0$ の重複度 = グラフの連結成分の数。

$\lambda_2$ — Fiedler 値(代数的連結性):

• $\lambda_2 > 0$ なら連結
• $\lambda_2$ が大きいほど 強く連結(切れにくい)
• $\lambda_2$ が小さいと ほとんど切れている(脆弱)

T 理論的解釈:集団の凝集性は Fiedler 値で測られる。High Shared 結合 ⇔ Fiedler 値が大きい。

拡散方程式と Laplacian

Laplacian は 離散版の拡散作用素:

$$ \frac{d\mathbf{x}}{dt} = -L \mathbf{x} $$

これは 熱方程式の離散版。情報・気分・気持ちが集合内を 拡散する動学を記述します。

Fiedler 値が大きいほど 拡散が速い(全員に伝わるのが早い)。

6B との対応

中級編で見た 6B の動学:

$$ \frac{dE_i}{dt} = (1 - E_i) \big[\rho_i B_i + (A \mathbf{E})_i\big] $$

線形化(平衡点近傍)すると:

$$ \dot{\mathbf{e}} \approx -\bar{L} \mathbf{e} + \text{(素地項)} $$

ここで $\bar{L}$ は 重み付き Laplacian(中級編の $A$ から構成)。

つまり 6B のダイナミクスは Laplacian の固有値スペクトルで支配される。

High Shared と spectral gap

Laplacian の spectral gap $\lambda_2 - \lambda_1 = \lambda_2$ が:

• 大きい:同期が早い、集団 E が一斉に上がる
• 小さい:同期が遅い、集団 E が分裂しがち

High Shared 結合 = spectral gap が大きい状態。これが 6B 「全員 E → 1」の数理的根拠。

Cheeger 不等式

グラフの isoperimetric constant $h(G)$(切断比):

$$ h(G) = \min_{S \subset V, |S| \le N/2} \frac{|\partial S|}{|S|} $$

ここで $|\partial S|$ は集合 $S$ から外への切断重み。

Cheeger 不等式:

$$ \frac{h(G)^2}{2} \le \lambda_2 \le 2 h(G) $$

Fiedler 値 $\lambda_2$ と切断比 $h(G)$ が 同程度のオーダー。

T 理論的含意:集団を分裂させようとする力の大きさ($h(G)$)が、集団の凝集性($\lambda_2$)を決める。

Random Walk と PageRank

Laplacian は ランダムウォークにも関連します:

$$ P = D^{-1} A \quad \text{(遷移確率行列)} $$

ノード $i$ から $j$ への遷移確率 $P_{ij} = w_{ij} / d_i$。

長時間極限の分布($\mathbf{1}^\top P \mathbf{x} = \mathbf{x}^\top$)が stationary distribution。

PageRank はこの spectral 構造を使ったアルゴリズム。T 理論的には、集団内の影響力の分布が PageRank 的に計算可能。

Spectral Clustering

Laplacian の固有ベクトル(spectral embedding)を使って、集団を クラスタに分割できます。

手順:

1. $L$ の最小固有ベクトル(最初の $k$ 個)を取る
2. これらをノードの座標として埋め込む
3. K-means クラスタリングを適用

T 理論的応用:大規模集団を 下位グループに分解して、各グループの 6B 動学を独立に分析する道具。

動的同期 — Kuramoto モデル

集団の 位相同期を扱うのが Kuramoto モデル:

$$ \dot\phi_i = \omega_i + \frac{K}{N}\sum_j \sin(\phi_j - \phi_i) $$

ここで $\phi_i$ は位相、$\omega_i$ は固有振動数、$K$ は結合強度。

$K$ が閾値を超えると同期相転移(全員の位相が一致)。

T 理論的解釈:集団の 意見・気分・行動の同期が Kuramoto 型で記述できる。同期は High Shared 結合の動的表現。

大規模グラフの困難

実際の集団は数十〜数千ノードで、Laplacian の固有値計算は:

• $N \le 10^3$:直接可能
• $N \le 10^6$:疎行列専用アルゴリズム(Lanczos 法等)
• $N \ge 10^9$:近似的・分散計算

T 理論を 大規模組織(企業・国家)に適用する時、計算量が問題になります。Mean-field 近似(次章)が代替手段。

エキスパンダーグラフ

spectral gap が大きいランダムグラフを エキスパンダー(expander graph)と呼びます。性質:

• Fiedler 値 $\lambda_2 = \Omega(1)$($N$ に依存しない大きさ)
• 大規模でも分裂しにくい
• 情報の急速な拡散

T 理論的含意:理想的な High Shared 組織はエキスパンダー的構造を持つべき。具体的:

• 弱い結合の多様な組み合わせ(small-world property)
• 中央依存しない冗長性
• ボトルネックがない

開かれた研究問題

1. 動的グラフ($A$ が時間変化)の T 理論的扱い
2. 重み付き有向グラフ(非対称な影響関係)での Laplacian の意味
3. マルチレイヤーネットワーク(複数種類の関係)での 6B 拡張
4. 量子グラフ(後の章 §26 と接続)での T 理論

次章への接続

Spectral graph theory で集団の動学を捉える枠組みができました。次章では 大規模集団の動学を mean-field 近似で扱います。Lasry-Lions の Mean Field Games 理論を T 理論的に接続します。