logo

그래프와 그래프 사이의 편집 거리 📂그래프이론

그래프와 그래프 사이의 편집 거리

정의 1

버텍스의 유한집합 XX 와 유한한 알파뱃의 집합을 α\alpha 이라 하자. 여기서 알파뱃은 공백 혹은 널null을 포함한다고 간주한다. 버텍스 라벨링vertex labeling V:X→αV : X \to \alpha 와 에지 라벨링edge labeling E:X×X→αE : X \times X \to \alpha 에 대해 트리플 G=(X,V,E)G = (X, V, E) 를 그래프라 한다. G^=(X^,V^,E^)\hat{G} = \left( \hat{X}, \hat{V}, \hat{E} \right) 가 GG 의 서브 그래프라는 것은 다음의 세 가지 조건을 만족하는 것을 의미한다:

  • X^⊂X\hat{X} \subset X
  • ∀x∈X^\forall x \in \hat{X} 에 대해 V^(x)=V(x)\hat{V}(x) = V(x)
  • ∀(x,y)∈X^×X^\forall (x, y) \in \hat{X} \times \hat{X} 에 대해 E^(x,y)=E(x,y)\hat{E} \left( x , y \right) = E \left( x , y \right)

ecgm

G1=(X1,V1,E1)G_{1} = \left( X_{1}, V_{1}, E_{1} \right) 과 G2=(X2,V2,E2)G_{2} = \left( X_{2}, V_{2}, E_{2} \right) 가 두 그래프라고 하자. 이들의 서브그래프 G^1=(X^1,V^1,E^1)\hat{G}_{1} = \left( \hat{X}_{1}, \hat{V}_{1}, \hat{E}_{1} \right) 와 G^2=(X^2,V^2,E^2)\hat{G}_{2} = \left( \hat{X}_{2}, \hat{V}_{2}, \hat{E}_{2} \right) 에 대해 전단사 f:X^1→X^2f : \hat{X}_{1} \to \hat{X}_{2} 를 G1G_{1} 에서 G2G_{2} 로의 에러-정정 그래프 매칭error-correcting graph matching이라 한다.

ecgm의 코스트

편의상 에지 라벨링의 레인지 E^k(X^k×X^k)\hat{E}_{k} \left( \hat{X}_{k} \times \hat{X}_{k} \right) 를 E^k\hat{E}_{k} 이라 나타내자. G1G_{1} 에서 G2G_{2} 로의 ecgm f:X^1→X^2f: \hat{X}_{1} \to \hat{X}_{2} 의 코스트cost c(f)c(f) 는 다음과 같이 정의된다.

c(f):=∑x∈X^1cvs(x)+∑x∈X1∖X^1cvd(x)+∑x∈X2∖X^2cvi(x)+∑e∈E^1ces(x)+∑e∈E1∖E^1ced(x)+∑e∈E2∖E^2cei(x) \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*}

  • cvs(x)c_{\text{vs}} (x) 는 x∈X^1x \in \hat{X}_{1} 을 f(x)∈X^2f(x) \in \hat{X}_{2} 으로 바꾸는 비용이다.
  • cvd(x)c_{\text{vd}} (x) 는 x∈X1∖X^1x \in X_{1} \setminus \hat{X}_{1} 을 G1G_{1} 에서 삭제하는 비용이다.
  • cvi(x)c_{\text{vi}} (x) 는 x∈X2∖X^2x \in X_{2} \setminus \hat{X}_{2} 을 G2G_{2} 에 추가하는 비용이다.
  • ces(x)c_{\text{es}} (x) 는 e=(x,y)∈E^1e = (x,y) \in \hat{E}_{1} 을 (f(x),f(y))∈E^2\left( f(x), f(y) \right) \in \hat{E}_{2} 으로 바꾸는 비용이다.
  • ced(x)c_{\text{ed}} (x) 는 e∈E1∖E^1e \in E_{1} \setminus \hat{E}_{1} 을 G1G_{1} 에서 삭제하는 비용이다.
  • cei(x)c_{\text{ei}} (x) 는 e∈E2∖E^2e \in E_{2} \setminus \hat{E}_{2} 을 G2G_{2} 에 추가하는 비용이다.

편집 거리

두 그래프 G1G_{1} 와 G2G_{2} 의 편집 거리edit distance d(G1,G2)d \left( G_{1} , G_{2} \right) 는 G1G_{1} 에서 G2G_{2} 로의 ecgm의 코스트 중 최소값으로 정의된다: d(G1,G2):=min⁡{c(f):f is an ecgm from G1 to G2} d \left( G_{1} , G_{2} \right) := \min \left\{ c(f) : f \text{ is an ecgm from } G_{1} \text{ to } G_{2} \right\}

설명

일반적인 정의를 따라가다보니 말이 지나치게 장황해진 느낌이 있는데, 개념적으로는 아주 쉽고 간단하다.

예로써 위와 같은 두 그래프가 있고 추가, 삭제, 교체의 코스트가 모두 11 이라면 한 쪽 그래프에 버텍스와 에지를 추가, 삭제, 교체하며 다른 쪽 그래프를 만들 수 있는 방법 중 가장 최소 횟수가 바로 그래프 편집 거리다. 위 경우엔 왼쪽에서 오른쪽 그래프를 만들기 위해 하나의 버텍스를 추가해야하며, 이미 있던 에지 중 하나를 새로운 노드로 잇는 교체가 필요하므로 그래프 편집 거리는 22 다.

같이보기

  1. Bunke. (1997). On a relation between graph edit distance and maximum common subgraph. https://doi.org/10.1016/S0167-8655(97)00060-3 ↩︎