[NetworkX] Projected Graph 투영그래프 (Bipartite Graph 활용)

Projected Graph 투영 그래프

https://en.wikipedia.org/wiki/Bipartite_network_projection

X, Y 집단(set)로 이루어진 Bipartite Graph에서,

X나 Y 둘 중 하나의 집단을 기준으로 투영한 그래프를 Projected Graph라고 합니다.

 

여기서 투영(projection)이란, 

두개의 집단으로 나누어져 있어 복잡한 그래프(a)의 정보를 (b)나 (c)처럼 압축하는 과정을 의미합니다.

 

기존의 그래프가 (X1)-(Y1)-(X2), (X2)-(Y4)-(X4) 와 같은 형식이였다면,

중간의 Y집단을 생략하고 (X1)-(X2), (X2)-(X4)와 같이 정보를 단순화 시키는 겁니다.

 

같은 집단 내부에서도 서로 가깝고 먼 노드들이 있을텐데,

노드 간의 관계를 파악하기에  유용합니다.

 

 

import networkx as nx
from networkx.algorithms import bipartite

X = set([1,2,3,4,5,6,7,8])
Y = set(['A','B','C','D','E','F'])

B = nx.Graph()

B.add_nodes_from(X, bipartite=0)
B.add_nodes_from(Y, bipartite=1)
B.add_edges_from([
    (1,'A'),(1,'B'),(2,'A'),(2,'B'),(2,'D'),(3,'C'),(3,'E'),(4,'A'),(4,'D'),
    (5,'C'),(5,'E'),(6,'C'),(6,'F'),(7,'E'),(7,'F'),(8,'E')
])

원래의 그래프 (a)

1. 단순투영

X-projection

G1 = bipartite.projected_graph(B, X)
nx.draw_networkx(G1)

X 집단 기준 투영 (b)

Y-projection

G2 = bipartite.projected_graph(B, Y)
nx.draw_networkx(G2)

Y 집단 기준 투영 (c)

 

2. 가중투영

1. 단순 투영은 각 노드가 얼마나 가까운지 정보가 누락된다는 문제가 있습니다.

때문에 가중투영에서는 엣지에 가중치 속성을 부여합니다.

 

여기서의 가중치는 두 노드가 원본 그래프에서 얼마나 많은 이웃을 가지고 있었는지를 의미합니다.

X-projection

G1 = bipartite.weighted_projected_graph(B, X, ratio=False)  # ratio: 비율표기 vs 개수표기

pos=nx.spring_layout(G1)
weight = nx.get_edge_attributes(G1, 'weight')

nx.draw(G1,pos,with_labels=True)
nx.draw_networkx_edge_labels(G,pos, edge_labels=weight)