📂グラフ理論

グラフ間のスペクトル距離

定義

頂点の数が $n$ の二つのグラフ $G_{1}$、$G_{2}$ の隣接行列をそれぞれ $A_{1}$、$A_{2}$ とする。これらが降順でソートされた固有値、すなわちスペクトラ^spectraをそれぞれ次のように示す。 $$ A_{1} \mapsto \lambda_{1}^{(1)} \ge \cdots \ge \lambda_{n}^{(1)} \\ A_{2} \mapsto \lambda_{1}^{(2)} \ge \cdots \ge \lambda_{n}^{(2)} $$ 二つのグラフ間のスペクトル距離^{spectral distance}を次のように定義する^{1 2}。 $$ d \left( G_{1} , G_{2} \right) := \sqrt{ \sum_{k=1}^{n} \left( \lambda_{k}^{(1)} - \lambda_{k}^{(2)} \right)^{2} } $$

説明

一見すると、グラフの距離は隣接行列自体のハミング距離で定義しても良さそうだが、単純に行列を成分ごとに比較することは頂点の順序に弱い。一方で、スペクトル距離はその定義上、ラベリングと無関係に定義されるという利点がある。