그래프의 종류

Contents

 

Heterogeneous Graph

이전까지의 그래프는 Homogeneous Graph로 노드가 단 하나의 속성 만을 가지고 있었다. 예를 들면, 사람과 사람 혹은 도시와 도시 간의 관계 만을 고려한 것이다. 반면에 Heterogeneous Graph는 노드가 여러 속성을 가지고 있는 것이다. 예를 들어 어떤 노드는 영화 정보를 가지고 있고, 어떤 노드는 고객 정보를 가지고 있는 형태를 의미한다. 이처럼 여러 속성을 가지고 있다면 추천을 적용할 때 보다 정확한 추천을 제공할 수 있을 것이다. 

Heterogeneous Graph

추천 시스템에서는 고객-제품 행렬을 기반으로 시스템을 구축하고 있다. 이 때 고객과 제품 뿐만 아니라 여러가지 정보들을 추가해서 입력할 수 있을 것이다. 

 

 

Bipartite Graph

이분 그래프(Bipartite praph)는 그래프 형태의 자료구조인데, 노드를 2개의 그룹으로 나눌 수 있으나 같은 그룹의 노드 끼리는 엣지(Edge)으로 연결되어 있지 않은 경우를 의미한다. 참고로 엣지는 아예 없고 노드만 있는 경우에도 이분 그래프라고 할 수 있다. 

 

Bipartite Graph

 

이와 같은 그래프는 추천 시스템을 공부하는 사람이라면 무수히 많이 접해보았을 것이다. 고객과 제품 간의 관계를 살펴보면 각 고객이 어떠한 제품을 선호하는지 그래프를 그리는 것 역시 이분 그래프라고 한다. 

 

Multidimensional Graph

다차원 그래프(Multidimensional Graph)는 둘 이상의 관계가 있는 그래프를 의미한다. 고객과 제품 간의 관계에서는 선호라는 관계 하나만 존재한다. 그러나 남편과 아내의 관계는 다르다. 남편과 아내는 여러 관계가 결합되어 있을 것이다. 이러한 복잡한 관계를 풀어 해석할 수 있다면 많은 정보를 획득할 수 있을 것이다. 이때 관계는 서로 독립적이어야 한다. 이러한 다차원 그래프는 둘 사이의 관계가 복잡한 소셜 네트워크에서 주로 사용된다. 

 

 

Signed Graph

부호 그래프(Signed Graph)는 그래프의 엣지에 긍정(positive)과 부정(negative)이 존재한다. 부호 그래프는 소셜 네트워크에서 주로 사용되며, 사용자를 팔로우 한다면 긍정 엣지로 표현하고, 언팔로우하거나 차단한다면 부정 엣지로 표현할 수 있다. 

Signed Graph

 

 

Hypergraph

이전까지는 모든 노드들이 연결되어 있다는 것을 가정으로 시작했다. 그러나 실제 환경에서는 하이퍼 그래프(Hypergraph)의 구조를 많이 갖고 있다. 아래의 그림처럼 색으로 표시된 부분은 하이퍼 그래프 내부에서 2개 이상의 노드를 연결해주는 엣지를 하이퍼 엣지라 부른다. 하이퍼 엣지는 각 노드들이 가진 공통점으로 볼 수 있다. 

 

위 경우와는 달리 하이퍼 엣지에 속한 노드의 수(cardinality)가 K개로 동일한 경우 K-uniform Hypergraph라 부른다.

 

Dynamic Graph

동적 그래프(Dynamic Graph)는 말 그대로 매 순간을 포착하면서 그래프가 변화하는 것을 의미한다. 지금까지 위에서 언급한 그래프는 모두 정적 그래프였다. 그러나 소셜 네트워크 데이터 혹은 트래픽과 같은 데이터는 실시간으로 변화한다. 노드와 엣지는 시간과 관련 있기 때문에 동적 그래프도 주로 사용된다. 만약 소셜 네트워크에 사용자가 처음 가입하게 되면 연결된 엣지는 0이다. 당연히 Degree도 0이 될 것이다. 이때 사용자가 다른 사람들을 팔로우하게 되면 엣지가 생기고 Degree가 증가한다. 이러한 과정이 즉각적으로 반영되어야 제대로 된 정보를 제공할 수 있을 것이다.