[graph] 그래프의 다양한 local overlap index 정리

요즘 그래프 이론을 공부중이다. 동기가 추천해줘서 일단 기초 서적을 읽고 있는데, 아무래도 그래프에 관한 '이론'은 처음 제대로 공부 중이라 어려운 부분이 많다.

그래도 이론 공부를 하면서 이렇게 틈틈이 기록해 두면 기억에 오래 남을 것 같아서 개인적으로 나에게 중요한 부분만큼은 공부한 내용을 간단하게 나마 기록해두려고 한다. 

현재 읽고 있는 책은 바로 이 책이다.

챕터 1은 스탠포드 cs224w을 수강하면서 나왔던 그래프의 기본 of 기본이고, 챕터 2부터 기록해둘 만한 내용이 나오고 있다. 

그 중에서도 오늘 포스팅 할 내용은 챕터 2의 2.2 Neighborhood Overlap Detection이다. 

 

 

---

 

2.1의 Graph Statistics and Kernel Methods에 소개된 방법들은 노드나 그래프 전체의 피쳐를 추출 및 그래프 분류에는 유용할 수 있지만 노드 간 관계성을 정량화할 수 없다는 단점이 있다. 노드 간 관계성이란 결국 노드1과 노드2가 얼마나 유사한가, 를 의미하는데 노드 간 유사성은 노드1과 노드2 사이에 중첩되는 이웃에 관한 문제이다 -- "neighborhood overlap between pairs of nodes, which quantify the extent to which a pair of nodes are related." 

 

노드 간 이웃의 중첩을 계산하는 데에 특별히 머신러닝 기법이 사용될 필요는 없지만, 중첩 이웃 탐색은 노드-노드 관계 예측에 중요한 베이스라인이 될 수 있다. 한 마디로 중첩을 계산하는 데에 복잡한 머신러닝이 사용되지는 않지만 관계를 알아내는 데에 이보다 가장 근본적인 방법은 없다는 것 같다. 구관이 명관이라는 말 인듯... 

 

Local overlap statistics are simply functions of the number of common neighbors rwo nodes share, i.e.
|N (u) ∩ N (v)|.

 

 위의 인용은 책의 18p에 나와있는 local overlap statistic에 대한 정의를 갖고온 것이다. 그리고 다음 목록은 local overlap statistic을 계산하는 다양한 계수에 대한 목록이다.  local overlap statistic은 결국 두 노드가 얼마나 비슷하냐? 유사한가?를 계산하는 일이기에 다음 계수들은 유사도를 측정하는 계수들이다. 

 

• Sørensen Index: 노드u와 노드v의 유사도는 (노드u와 노드v의 중첩 이웃 노드의 수)x2 / (노드u와 노드v의 디그리)이다. 노드 디그리로 나누어주는 것은 일종의 일반화인데, 이러한 일반화 계산이 중요한 이유는 'overlap measure would be highly biased towards predicting edges for nodes with large degrees' 라고 한다. 

• Salton Index (cosine similarity): 위와 비슷하게 중첩 노드의 개수를 정량화하고 두 노드의 디그리로 나눠줌으로써 일반화하는 또 다른 계수이다.

• Jaccard Index: 요것도 위와 비슷. 

• Resource Allocation (RA) Index: 중첩 이웃노드의 갯수를 세고, 중첩 이웃노드의 중요도를 고려한 계수이다. RA 계수 같은 경우, u라는 v1과 v2의 중첩 이웃노드의 inverse degrees를 계산하였다. 

• Adamic/Adar Index: RA 계수와 비슷한데 log inverse degrees를 계산함. RA계수와 AA계수는 디그리가 낮은 중첩 이웃노드에 weight를 줬다. 요컨대 v1과 v2의 중첩 이웃노드 중 low-degree 이웃노드가 더 informative하단 intuition이다. 예를 들어 어떤 친구와 내가 공통적으로 알고 있는 친구A가 있는데, 이 친구A에게 우리 말고 다른 친구가 없을 경우 (low-degree)에 친구A가 우리에게 주는 정보가 더 많다는 뜻이다. 또 다른 공통 친구B는 우리 이외에도 다른 친구가 많다면 친구B가 알고 있는 정보들은 친구B의 다른 친구들에게 퍼져퍼져 나가 우리에게도 어쩌면 전해져 왔을 수 있지만.. 친구A 같은 경우, 친구A의 친구가 우리밖에 없기 때문에 친구A가 주는 정보는 유니크하고, 더 귀한 정보일 것이다. 뭐, 난 이렇게 이해했다.