グラフの隣接行列とスペクトルグラフ理論

1. 隣接行列（Adjacency Matrix）

グラフ理論において、隣接行列はグラフ構造を線形代数的に表現するための基本的な方法です。

• 定義: 頂点数が $n$ のグラフ $G = (V, E)$ に対して、隣接行列 $A \in \mathbb{R}^{n \times n}$ は次のように定義されます。

  $$A_{ij} = \begin{cases} 1 & (i, j) \in E \\ 0 & (i, j) \notin E \end{cases}$$

  無向グラフの場合、$A$ は対称行列になります。

• 性質:

  • $A^k$ の $(i, j)$ 成分は、頂点 $i$ から頂点 $j$ への長さ $k$ の道の本数を表します。

  • グラフの構造（連結性やサイクルの有無）を解析するための基本的ツールです。

2. スペクトルグラフ理論（Spectral Graph Theory）

スペクトルグラフ理論は、グラフに対応する行列（隣接行列、ラプラシアン行列など）の固有値と固有ベクトルを利用して、グラフの性質を研究する分野です。

(1) 隣接行列の固有値

• 隣接行列 $A$ の固有値は、グラフの構造を反映します。

  • 最大固有値はグラフの密度や次数分布と関係します。

  • 固有値の多重度は、グラフの対称性や連結成分の数と関係します。

(2) グラフラプラシアン

隣接行列と次数行列（$D = \text{diag}(d_1, d_2, \dots, d_n)$, 各 $d_i$ は頂点 $i$ の次数）から構成される行列です。

$$L = D – A$$

• 性質:

  • $L$ は対称かつ半正定値行列。

  • 固有値は非負。

  • 最小固有値は常に 0 で、その重複度は連結成分の個数に一致。

(3) 応用例

• クラスタリング（コミュニティ検出）:
  ラプラシアンの固有ベクトルを利用する「スペクトルクラスタリング」では、グラフを自然に分割できます。

• ネットワーク解析:
  固有値分布からネットワークの「拡散性」や「脆弱性」を評価できます。

• ランダムウォーク:
  ラプラシアンの固有構造は、マルコフ連鎖やランダムウォークの収束性と関係します。

3. コンピュータサイエンスにおける応用

• 検索エンジン（PageRank）: 隣接行列を正規化した確率行列を使い、ウェブグラフ上でランダムサーファーの分布を求めます。

• 機械学習: グラフニューラルネットワーク（GNN）では、ラプラシアン固有分解に基づくフィルタ設計が理論的基盤となっています。

• 画像処理: 画像をピクセルグラフに変換し、ラプラシアン固有ベクトルを使った分割（セグメンテーション）に利用されます。

---

まとめると、隣接行列はグラフの基本的な線形代数的表現であり、スペクトルグラフ理論はその固有値・固有ベクトルを通じてグラフ構造を解析する強力な方法です。これにより、ネットワーク解析やクラスタリング、検索アルゴリズムなど、コンピュータサイエンスの幅広い分野で応用されています。