Link Prediction Task
- New Links를 예측
- 원래 존재하던 edge를 제외한 모든 노드의 edge를 ranking하고 top K개의 Link를 예측
- Feature design의 key는 pair of nodes
링크 예측은 크게 두가지로 나뉨
-
Links missing at random
무작위로 link를 제거하고 ML 알고리즘으로 예측 -
Links over time
시간에 따라 점차 링크가 생겨날 것이라는 것 (SNS, Transaction) 등
그래서 먼저 생길 Link 들을 예측한다는 마인드
동적 네트워크에 유리
Methodology
- (x,y)에 공통적으로 포함된 노드의 수를 찾는 함수 c(x,y)를 정의
- sort
- top n pairs will be new link!
Link-Level Features
Describe relationship between two nodes
Shortes-path distance between two nodes
- 두 노드 사이의 최단 거리
- 간단, 강력한 지표이지만 두 노드간의 Clustering 계수 등 연결의 강도를 측정하지는 못함
Local Neighborhood Overlap
common neighbors
- 이웃의 교집합 원소 수
Jaccard's coefficient
- 이웃 교집합 원소 수 / 이웃 합집합 원소 수
Adamic-Adar index
- Ku는 k의 차수로서 교집합 원소의 차수가 낮을 수록 이웃이 끈끈하다는 가정
소셜 네트워크에서 잘 작동
Limitation
- 공통 이웃이 없는 경우 언제나 0을 반환한다는 것
- 2 hops 이상 떨어져 있으면 언제나 0임, 이들은 언젠가 붙을 수 있음에도 불구하고.. 이를 해결하기 위해
Global neighborhood overlap
- Katz index
주어진 노드 쌍 사이의 모든 길이가 다른 경로의 수를 계산
어떻게 path의 개수를 계산하나요? 인접행렬!
A^k는 k length인 인접행렬이니 몇 개인지 구할 수 있음
인접행렬의 행렬곱이 노드간의 거리를 제공한다는 것
A^1, A^2로 모든 길이가 같은 다른 경로의 수를 구하고 베타라는 weight factor를 통해 계산
최종적으로 이것은 기하 행렬이기에, 다음과 같은 수식으로 정리 됨
Summary
거리 feature, 이웃 재생산 feature, Global 이웃 overlap feature를 통해 Link 예측에 도움을 주는 feature 들을 만들어냄
세상아 덤벼라