[CS224W] 2.2 Traditional Feature-based Methods: Link

박상우·2023년 2월 10일
0

CS224W

목록 보기
11/11
post-thumbnail
  • 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!

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 들을 만들어냄

profile
세상아 덤벼라

0개의 댓글