[NetwrokX] 어떤 노드들이 새로 친구가 될까? Link Prediction #1

---

지난 글에서는 새로 들어온 노드가 어떤 노드와 연결이 될지를 확률적으로 계산하는 Preferential Attatchment Model을 알아보았습니다.

[NetworkX] 새로운 노드는 어디에 어떤 노드와 연결될까?Preferential Attachment Model (Barabasi Albert Model)

 

새로 edge, link가 생성되는 경우로는 전학생(새로 추가된 노드)이 오는 경우만 있지 않습니다.

기존 존재하던 node 사이에서 edge가 새로 생성되는 과정

이미 같은 반이였던 동급생끼리도 친구가 될 수 있습니다.

기존 네트워크 그래프에서 node의 개수는 그대로인 상태로 edge가 새로 생성되는거죠.

 

X라는 노드가 있고, 이 노드가 새로 관계를 생성한다고 할 때,

X는 누구와 edge(혹은 link)를 생성할까요?

 

어떤 엣지, 링크가 새로 생성될지 예측해봅시다. (Link Prediction)

 

 

방법1. 공통이웃을 얼마나 가지고 있는가?

가장 쉬운 방법 중 하나입니다.

공통된 이웃을 많이 가지고 있다면 더 쉽게 관계를 맺을 수 있을겁니다.

어쩌면 이미 친구일 수도 있겠죠.

 

이 방법에 의하면, (A)는 직접 연결되지 않은 [C,F,G,H,I] 중, (C)와 가장 많은 공통 이웃을 공유하고 있습니다.

즉, (C)와 새롭게 edge를 연결할 가능성이 가장 높다고 볼 수 있습니다.

 

# 이 문서에서는 이 그래프를 계속 사용합니다.
import networkx as nx

edges = [('A','B'),('A','D'),('A','E'),('B','D'),('B','C'),('C','D'),('C','F'),
         ('E','F'),('E','G'),('F','G'),('G','H'),('G','I')]

G = nx.Graph()
G.add_edges_from(edges)

# 엣지 연결이 없는 노드쌍
non_edges = list(nx.non_edges(G))
# 출력
[('C', 'H'),
 ('C', 'G'),
 ('C', 'E'), 생략

# 공통이웃 수 count 딕셔너리 생성
common_neighbors_count = {}
for n1,n2 in non_edges:
    common_neighbors_count[(n1, n2)] = len(list(nx.common_neighbors(G, n1, n2)))

sorted(common_neighbors_count.items(), key=lambda x: x[1], reverse=True)
# 출력
[(('C', 'A'), 2),
 (('C', 'G'), 1),
 (('C', 'E'), 1), 생략

('C','A')의 공통이웃 수가 2로, 가장 많음을 확인할 수 있습니다.

 

 

방법2. 자카드 계수 (Jaccard Coefficient)

단순하게 방법1처럼 공통이웃의 절대숫자만으로는 어려울 수 있습니다.

6,70년대 마냥 한 반의 학생 수가 엄청 많을 수도 있으니까요.

 

두루두루 아는 애들 많은 두명이 서로 친해지기보다는

오타쿠 같은 친구들 몇 없는 애들끼리 몇명 모이다가 서로 친해지는게 더 수월할 수 있습니다.(자기소개ing)

 

자카드 계수(Jaccard Coefficient)는 두 집합 사이의 유사도를 측정하는 방법입니다.

자카드 지수(Jaccard index), 자카드 유사도(Jaccard similarity)라고도 부릅니다.

 

A와 C의 이웃 합집합은 {B,D,E,F} 4명, 교집합은 {B,D} 2명이므로, 자카드 계수는 0.5 입니다.

jaccard = list(nx.jaccard_coefficient(G))
jaccard.sort(key=lambda x: x[2], reverse=True)  # 정렬
# 출력
[('H', 'I', 1.0),
 ('C', 'A', 0.5),
 ('F', 'H', 0.3333333333333333),

('H','I')의 자카드계수가 1로, 가장 높음을 확인할 수 있습니다.

 

 

방법3. 자원할당 Resource Allocation 

자원이 얼마나 할당되고 전달되는가를 기준으로도 생각해볼 수 있습니다.

 

여기서 자원할당이란,

(X)가 공통이웃(Z)에게 1을 전달했을 때, 전체 1 중 얼마나 많은 값이 (Y)에게 전달 될 것이냐 입니다.

 

물론 위에서 예시로 들었던 "친구 사귀기"를 빗대어 생각해볼 때, "자원할당"이라고 하면 좀 이상해지긴 합니다.

그냥 그런거라 칩시다

아무튼, 위와 같은 방식에서라면 중간에 끼어있는 공통이웃(Z)가 얼마나 많은 degree를 가지고 있느냐에 따라 전달되는 자원의 값은 달라질 것입니다.

즉,

• 공통이웃 숫자가 많을수록(Z1,Z2,Z3,...),
• 공통이웃(Z)이 우리(X,Y) 말고는 또다른 이웃을 가지지 않을수록

전달되는 자원의 양은 많아집니다.

resource = list(nx.resource_allocation_index(G))
resource.sort(key=lambda x: x[2], reverse=True)  # 정렬
# 출력
[('C', 'A', 0.6666666666666666),
 ('C', 'G', 0.3333333333333333),
 ('C', 'E', 0.3333333333333333),

('C','A')간의 자원할당량이 0.6666...로, 가장 높음을 확인할 수 있습니다.

 

 

방법4. Adamic-Adar Index

Adamic Adar 방법은 방법3. 자원할당과 매우 흡사합니다.

똑같이 자원을 할당하긴 하되, 방법3에서는 degree로 자원이 깎여 나갔다면

Adamic Adar에서는 log(degree)로 자원이 깎입니다.

 

degree가 높다고 자원이 팍팍 깎여 나가는 정도가 덜해진 것 뿐입니다.

A,C간 자원의 전달량이 0.6666 에서 1.82로 뛰었습니다.

resource = list(nx.adamic_adar_index(G))
resource.sort(key=lambda x: x[2], reverse=True)  # 정렬
# 출력
[('C', 'A', 1.8204784532536746),
 ('C', 'G', 0.9102392266268373),
 ('C', 'E', 0.9102392266268373),

 

 

방법5. Preferential Attachment Model (바라바시 알베르트 모델)

위에서 나왔던 방법들과는 조금 다르게,

이미 친구가 많은 인싸들끼리 친해질 수도 있습니다.

이전 글에서 다루었던 Preferential Attachment Model (Barabasi Albert Model)을 활용하면 계산할 수 있습니다.

[NetworkX] 새로운 노드는 어디에 어떤 노드와 연결될까?Preferential Attachment Model (Barabasi Albert Model)

pref = list(nx.preferential_attachment(G))
pref.sort(key=lambda x: x[2], reverse=True)  # 정렬
# 출력
[('D', 'G', 12),
 ('A', 'G', 12),
 ('G', 'C', 12),