📂グラフ理論

グラフとグラフの間の編集距離

定義 ¹

頂点の有限集合 $X$ と有限なアルファベットの集合を $\alpha$ としよう。ここでアルファベットは空白またはヌル^nullを含むとする。頂点ラベリング^{vertex labeling} $V : X \to \alpha$ とエッジラベリング^{edge labeling} $E : X \times X \to \alpha$ により、トリプル $G = (X, V, E)$ をグラフという。$\hat{G} = \left( \hat{X}, \hat{V}, \hat{E} \right)$ が $G$ のサブグラフであるとは、以下の三つの条件を満たすことを意味する：

• $\hat{X} \subset X$
• $\forall x \in \hat{X}$ に対して $\hat{V}(x) = V(x)$
• $\forall (x, y) \in \hat{X} \times \hat{X}$ に対して $\hat{E} \left( x , y \right) = E \left( x , y \right)$

ecgm

$G_{1} = \left( X_{1}, V_{1}, E_{1} \right)$ と $G_{2} = \left( X_{2}, V_{2}, E_{2} \right)$ を二つのグラフとする。これらのサブグラフ $\hat{G}_{1} = \left( \hat{X}_{1}, \hat{V}_{1}, \hat{E}_{1} \right)$ と $\hat{G}_{2} = \left( \hat{X}_{2}, \hat{V}_{2}, \hat{E}_{2} \right)$ に対し、全射 $f : \hat{X}_{1} \to \hat{X}_{2}$ を $G_{1}$ から $G_{2}$ へのエラー訂正グラフマッチング^{error-correcting graph matching}という。

ecgmのコスト

便宜上、エッジラベリングの範囲 $\hat{E}_{k} \left( \hat{X}_{k} \times \hat{X}_{k} \right)$ を $\hat{E}_{k}$ と表す。$G_{1}$ から $G_{2}$ へのecgm $f: \hat{X}_{1} \to \hat{X}_{2}$ のコスト^cost $c(f)$ は次のように定義される。

$$ \begin{align*} c(f) :=& \sum_{x \in \hat{X}_{1}} c_{\text{vs}} (x) + \sum_{x \in X_{1} \setminus \hat{X}_{1}} c_{\text{vd}} (x) + \sum_{x \in X_{2} \setminus \hat{X}_{2}} c_{\text{vi}} (x) \\ & + \sum_{e \in \hat{E}_{1}} c_{\text{es}} (x) + \sum_{e \in E_{1} \setminus \hat{E}_{1}} c_{\text{ed}} (x) + \sum_{e \in E_{2} \setminus \hat{E}_{2}} c_{\text{ei}} (x) \end{align*} $$

• $c_{\text{vs}} (x)$ は $x \in \hat{X}_{1}$ を $f(x) \in \hat{X}_{2}$ へ変更するコストである。
• $c_{\text{vd}} (x)$ は $x \in X_{1} \setminus \hat{X}_{1}$ を $G_{1}$ から削除するコストである。
• $c_{\text{vi}} (x)$ は $x \in X_{2} \setminus \hat{X}_{2}$ を $G_{2}$ に追加するコストである。
• $c_{\text{es}} (x)$ は $e = (x,y) \in \hat{E}_{1}$ を $\left( f(x), f(y) \right) \in \hat{E}_{2}$ へ変更するコストである。
• $c_{\text{ed}} (x)$ は $e \in E_{1} \setminus \hat{E}_{1}$ を $G_{1}$ から削除するコストである。
• $c_{\text{ei}} (x)$ は $e \in E_{2} \setminus \hat{E}_{2}$ を $G_{2}$ に追加するコストである。

編集距離

二つのグラフ $G_{1}$ と $G_{2}$ の編集距離^{edit distance} $d \left( G_{1} , G_{2} \right)$ は、$G_{1}$ から $G_{2}$ へのecgmのコストの中で最小値で定義される： $$ d \left( G_{1} , G_{2} \right) := \min \left\{ c(f) : f \text{ is an ecgm from } G_{1} \text{ to } G_{2} \right\} $$

説明

一般的な定義に従うと話がやや長くなるが、概念的には非常に簡単である。

例として、上記のような二つのグラフがあるとし、追加、削除、交換のコストがすべて $1$ である場合、一方のグラフから頂点とエッジを追加、削除、交換して他方のグラフを作成する方法の中で最も少ない回数がまさにグラフ編集距離である

。上記の場合では、左側のグラフから右側のグラフを作るために1つの頂点を追加し、既存のエッジの1つを新しいノードに接続する交換が必要であるため、グラフ編集距離は $2$ である。

参照

• 文字列の編集距離
• グラフ間のスペクトル距離