[Stanford/CS224W] 1. intro(3) : 그래프 표현의 선택

스탠포드 강의를 듣고 정리한 내용입니다. 

그래프 표현 방법

앞의 포스팅에서는 그래프에는 어떤 종류가 있는지, 어떻게 활용될 수 있는지 알아보았습니다. 

이번 포스팅에서는 그래프를 어떻게 표현하는지에 대해서 알아보도록 하겠습니다. 



앞에서도 살짝 언급했듯이 그래프는 노드와 엣지로 구성되어있습니다. 이를 수학적 기호로 표현하면 아래와 같습니다. 

Objects : nodes, vertices → N

Interactions : link, edges → E

System : network, graph → G(N,E)

 

Directed Graph와 Undirected Graph

그래프의 종류에는 크게 Directed Graph와 Undirected Graph가 있습니다.

 

Directed Graph 

Directed Graph는 말 그대로 방향성이 있는 그래프입니다. 출발지와 목적지가 뚜렷한 그래프죠. 

위의 그림에서 보시는 것 처럼 엣지에는 화살표가 존재합니다. 이 그래프의 예시로는 전화 통화(수신,발신)와 트위터의 팔로잉, 팔로워가 있습니다. 

 

Undirected Graph

Undirected Graph는 방향성이 없는 그래프입니다. 노드간의 연결성만 중요시하는 그래프죠.

위의 그림에서 보시는 것 처럼 엣지에는 화살표가 없습니다. 이 그래프의 예시로는 페이스북의 친구 관계가 있습니다.

 

Node Degrees

노드의 Degree는 노드에 연결되어있는 엣지의 수를 뜻합니다. 이 말은 즉, 이 노드가 다른 노드랑 얼마나 연결되어있는지를 뜻합니다. 

Directed인지 Undirected인지에 따라 엣지의 수를 세는 방법이 다릅니다. 

Directed Graph 

방향성이 있는 그래프는 기준이 되는 노드에서 다른 노드로 향하는 엣지의 수를 out-degree 반대로 다른 노드에서 기준이 되는 노드로 향하는 엣지의 수를 in-degree라고 정의합니다. 위의 예로 노드 C의 in-degree는 2, out-degree는 1입니다. 

 

Undirected Graph

방향성이 없는 그래프는 그냥 주변 엣지 개수를 세주면 됩니다. 위의 예에서 노드 A의 degree는 4입니다. 

 

 

※ Bipartite Graph

엣지의 방향성과는 별개로 Bipartite Graph 라는 것이 있습니다. 이 그래프는 서로 다른 종류(카테고리)를 가지는 노드들과 엣지로 표현하는 그래프입니다. 그리고 자신과 다른 타입의 노드하고만 관계를 가지는 특성이 있습니다. 앞의 포스팅에서 설명한 heterogeneous graph의 개념이라고 보시면 됩니다. 

위의 예시를 보시면 하나의 그래프에 U, V타입의 노드가 존재하고, 각 노드들은 다른 타입의 노드하고만 관계가 있습니다. 

이 그래프의 예시로는 논문과 저자, 배우와 영화, 유저와 영화, 유저와 아이템 등이 있습니다. 

 

그래프의 수학적 표현 

위에서는 그래프를 표현하기 위해 어떤 그래프가 있는지 엣지의 관점에서 살펴보았습니다. 

이번에는 이 그래프를 어떻게 수학적으로 표현할 수 있는지 살펴보겠습니다. 수학적 표현 방법에서는 Undirected, Directed 모두 표현할 수 있습니다.

 

Adjacency Matrix

그대로 해석하면 인접행렬이죠. 관계가 있는 노드들은 1, 관계가 없는 노드들은 0으로 표기하여 하나의 행렬을 만들어 주는 것입니다. 

위의 예제를 보시면 이해하기 쉬우실겁니다. 예를 들어 1과 2의 관계성을 살펴봅시다. Directed에서는 1행 2열과 2행 1열의 수치가 다릅니다. 1행 2열은 노드1에서 노드2로 가는 엣지가 없기 때문에 0, 노드2에서 노드1로 가는 엣지는 있기 때문에 1이 됩니다. 반면 Undirected는 노드1과 노드2가 연결이 되어있기 때문에 1행 2열, 2행 1열이 모두 1로 같습니다. 

보시다싶이 Undirected Graph의 인접 행렬은 대각선을 기준으로 대칭을 이룹니다. 

 

인접행렬로 표현하는 것에 대한 장점은 굉장히 이해하기 쉽다는 것이죠. 

 

하지만!

실제 그래프를 살펴보면 연결된 노드보다 연결되지 않은 노드가 훨씬 많습니다. 그렇기 때문에 행렬의 대부분은 0으로 채워집니다.(sparse matrix) 따라서 메모리를 많이 사용하고, 계산량도 커지기 때문에 효율적으로 사용하기 어렵습니다. 

 

물론 크기가 작은 그래프라면 사용해도 상관없겠지만, 그래프 크기가 커질수록 낭비되는 메모리가 많아지겠죠?

 

Edge List

엣지 리스트는 서로 이어져 있는 시작, 도착 노드의 쌍으로 나타냅니다.

노드 2와 노드 3은 연결되어 있기 때문에 (2,3), (3,2)로 모두 표현할 수 있습니다. 

 

이 표현 방법은 2차원 행렬로 간단하게 표현할 수 있기 때문에 딥러닝에서 자주 사용되는 방법이라고 합니다. 

 

하지만!

그래프가 엄청 커질 경우 모든 리스트를 접근해야하기 때문에 분석하기가 매우 어렵다는 단점이 있습니다. 

 

Adjacency List

이 방법은 마치 파이썬의 딕셔너리를 떠오르게하는 방법인데요. 노드를 key로 두고 연결되는 다른 노드들을 value에 저장하는 형태입니다. 

이는 Edge가 기준이었던 위의 방법들과는 달리 각 노드에 접근하기 때문에 그래프의 크기와 상관 없이 가장 효율적이라고 할 수 있습니다. 

 

또 다른 옵션들 

지금까지는 엣지에 아무런 조건들이 없었습니다. 

하지만 실제로는 더 복잡한 문제를 다루기 위해 엣지에는 다음과 같은 옵션들이 추가될 수 있습니다. 

• weight
• ranking
• type
• sign

 

또 다른 그래프들

위에서는 엣지의 방향성을 기준으로 나누었는데요. 

그 외에 다른 그래프들도 있습니다.

self-edges : 자기 자신으로 가는 엣지가 있는 그래프

multigraph : 노드 사이의 관계가 여러개일 경우 

 

connected graph와 disconnected graph 

그래프 내의 노드들의 연결성에 따라 connected graph와 disconnected graph로 나눌 수도 있습니다. 

위의 그림에서 왼쪽은 모든 노드들이 연결되어 하나의 그래프를 이루고있죠? 이 그래프를 바로 connected graph라고 합니다. 

반면 오른쪽 그림은 연결되지 않은 노드들이 있습니다. 이렇게 하나의 그래프 내에서 연결되지 않은 노드들 때문에 두개, 세개로 쪼개지는 경우를 disconnected graph라고 합니다. 

 

Strongly graph와 Weakly graph

그래프 내에 서로가 순환할 수 있는지 없는지에 따라 strongly graph와 weakly graph로 나눕니다. 

위와 같이 서로를 순환하는 노드가 그래프 내에 존재하면 strongly graph입니다.