グラフラプラシアン行列（Graph Laplacian）は、グラフ理論やデータ解析、機械学習の分野で頻繁に使用される重要な概念です。グラフ構造に関連付けられた行列であり、クラスタリングやグラフ信号処理、ネットワーク分析などで活用されます。
グラフラプラシアン行列の定義
グラフラプラシアン行列は、与えられた無向グラフに対して構築される行列で、以下の式で定義されます。
$$L = D - A$$
ここで、
- **L: グラフラプラシアン行列 **
-
D: 次数行列（Degree Matrix）
グラフにおける各頂点の次数を対角成分に持つ行列です。 -
A: 隣接行列（Adjacency Matrix）
グラフにおける辺の接続関係を表す行列です。
隣接行列Aの定義
無向グラフ$G = (V, E)$ の隣接行列Aは次のようになります。
A_{ij} =
\begin{cases}
1 & (i, j) \in E \\
0 & (i, j) \notin E
\end{cases}
ここで E はグラフのエッジ集合、V は頂点集合です。
次数行列Dの定義
次数行列 (D) は、以下のように対角行列で表されます。
$$
D_{ii} = \text{deg}(v_i)
$$
ここで $\text{deg}(v_i)$ は頂点 $v_i$ の次数（隣接している辺の数）を表します。
これらを用いることで、
$$
L = D - A
$$
が得られます。
グラフラプラシアン行列の性質
1. 固有値とクラスタリング
グラフラプラシアン行列の固有値や固有ベクトルは、グラフのクラスタリングや分割に関連しています。特に、スペクトルクラスタリングに用いられます。
- スペクトルクラスタリングでは、固有ベクトルを用いてデータポイントをクラスタに分けることができます。
2. スペクトルギャップ
固有値の間にあるギャップ（スペクトルギャップ）も、グラフ分割の性質を示します。これにより、グラフの分断やクラスタリングの精度を解析できます。
3. 非負定値性
グラフラプラシアン行列 (L) は常に非負定値行列です。そのため、固有値がすべて非負であるという性質があります。
4. 連結性との関係
グラフが連結である場合、Lの固有値の最小値は0となります。つまり、
$$
\lambda_0 = 0
$$
が成り立ちます。そして、固有値0の数は連結グラフの個数を表します。
応用例
1. スペクトラルクラスタリング
グラフラプラシアン行列の固有ベクトルを用いて、データをクラスタリングする手法です。特に、隣接関係があるデータポイント群を分割するのに適しています。
2. ネットワーク分析
ソーシャルネットワークや通信ネットワークの解析において、ラプラシアン行列を使用することで、ネットワークの構造や中心性の評価が可能になります。
3. グラフ信号処理
グラフ信号処理では、ラプラシアン行列を用いて信号解析やデータ処理を行います。例えば、信号のノイズ除去やデータ圧縮に使用します。