🧐 Link Prediction algorithms
링크 예측이란 현재 네트워크에서 나타나지 않은 연결을 예측하거나 시간이 지나 미래의 네트워크에서는 새로 생겨나고 없어질 링크를 예측하는 것이다. 공통 이웃의 수와 같은 구조적 유사성 지표를 통해서 관측되지 않은 링크의 존재를 예측하는 방법이 일반적이다. 계산된 점수를 사용하여 그 사이의 새로운 관계를 예측할 수 있다.
1. Adamic Adar
공유 이웃을 기반으로 노드의 근접성을 계산한다.
N(u)은 u에 인접한 노드 집합으로, 결과 값이 높을수록 노드가 더 가깝다는 것을 나타낸다.
즉, 노드 A와 B간에 공통되는 이웃들이 많다고 하더라도, 이웃들의 degree가 매우 크다면 이 둘이 연결될 가능성은 낮다고 평가하는 것이다.
2. Common Neighbors
연결되어 있지 않은 두 노드들 간에 공통의 노드들이 공유된다면, 이 둘은 이후에 연결될 가능성이 높다는 것이다.
위의 공식에서 N(x)는 노드 x에 인접한 노드들의 집합이고, N(y)는 노드 y에 인접한 노드들의 집합이다. 결과 값이 높을수록 두 노드가 더 가깝다는 것을 나타낸다.
🙉 Practice in Neo4j!
1) 데이터 생성
CREATE
(zhen:Person {name: 'Zhen'}),
(praveena:Person {name: 'Praveena'}),
(michael:Person {name: 'Michael'}),
(arya:Person {name: 'Arya'}),
(karin:Person {name: 'Karin'}),
(zhen)-[:FRIENDS]->(arya),
(zhen)-[:FRIENDS]->(praveena),
(praveena)-[:WORKS_WITH]->(karin),
(praveena)-[:FRIENDS]->(michael),
(michael)-[:WORKS_WITH]->(karin),
(arya)-[:FRIENDS]->(karin)2) 'Michael', 'Karin'의 Adamic adar 지수
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN gds.alpha.linkprediction.adamicAdar(p1, p2) AS score-> 결과 score : 0.9102392266268373
3) 'Michael', 'Karin'의 Common Neighbors 지수
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN gds.alpha.linkprediction.commonNeighbors(p1, p2) AS score-> 결과 score : 1.0
