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

---

지난 글에서는 

기존 네트워크 그래프에서 node의 개수는 그대로인 상태로

어떤 edge가 새로 생성될지 예측하는 방법론을 다루어 보았습니다.

 

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

• 방법1. 공통이웃을 얼마나 가지고 있는가?
• 방법2. 자카드 계수
• 방법3. 자원할당
• 방법4. Adamic-Adar Index
• 방법5. Preferential Attachment Model

 

위의 방법들은 모두 하나의 반(동일한 community) 안에서 일어나는 일입니다.

 

하지만 현실에서는 서로 다른반인 경우에도 친구가 될 수 있죠.

물론 같은 반인 경우 친구가 될 가능성이 더 클겁니다.

 

이렇게 반이 다른 경우(서로 다른 community)도 반영해서 link prediction을 해봅시다.

[A,B,C,D] VS [E,F,G,H,I] 두개의 커뮤니티가 있다고 가정하겠습니다.

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')]
community0 = ['A','B','C','D']
community1 = ['E','F','G','H','I']

G = nx.Graph()
G.add_edges_from(edges)
G.add_nodes_from(community0, community=0)
G.add_nodes_from(community1, community=1)

G.nodes(data=True)
# 출력
NodeDataView({'A': {'community': 0}, 'B': {'community': 0}, 'D': {'community': 0}, 'E': {'community': 1}, 'C': {'community': 0}, 'F': {'community': 1}, 'G': {'community': 1}, 'H': {'community': 1}, 'I': {'community': 1}})

 

 

방법6. 공통이웃 + 커뮤니티 (C.N. Soundarajan-Hopcroft score)

이름은 cn_soundarajan_hopcroft로 거창하고 낯설지만, 계산식을 보면 매우 단순합니다.

[방법1. 공통이웃을 얼마나 가지고 있는가?]에서 덧셈이 하나 더 붙었을 뿐입니다.

 

식을 두개로 나눠서 봅시다.

1) 공통이웃의 수 : |N(X)∩N(Y)|

단순하게 (X)와 (Y)의 공통이웃 수를 먼저 구합니다. 방법1과 동일합니다.

2) 공통이웃이 같은 커뮤니티에 속하는가 : ∑ f(u)

공통이웃 (Z1), (Z2), ... 가 있다면, 

(X,Y,Z1)이 하나의 동일한 커뮤니티에 속하는가? (X,Y,Z2)이 하나의 동일한 커뮤니티에 속하는가? 를 체크합니다.

cn_s_h = list(nx.cn_soundarajan_hopcroft(G))
cn_s_h.sort(key=lambda x: x[2], reverse=True)  # 정렬

cn_s_h
# 출력
[('A', 'C', 4),  # 2+2
 ('F', 'I', 2),  # 1+1
 ('F', 'H', 2),  # 1+1

 

 

방법7. 자원할당 X 커뮤니티 (R.A. Soundarajan-Hopcroft score)

이 방법 역시 이전 글에서 다루었던 자원할당 방법과 매우 유사합니다.

분자에 있던 1 대신 f(u)가 들어왔을 뿐입니다.

 

f(u)는 위의 방법6과 마찬가지로, 

같은 커뮤니티 안에 있으면 1, 같은 커뮤니티가 아니라면 0으로 처리됩니다.

 

즉, 서로 다른 커뮤니티라면 계산에 반영하지 않고,

같은 커뮤니티끼리의 자원할당만을 계산하겠다는뜻입니다.

ra_s_h = list(nx.ra_index_soundarajan_hopcroft(G))
ra_s_h.sort(key=lambda x: x[2], reverse=True)  # 정렬

ra_s_h
# 출력
[('A', 'C', 0.6666666666666666),
 ('F', 'I', 0.25),
 ('F', 'H', 0.25),