NetworkX로 그래프 쿼리하기

NetworkX로 그래프 쿼리하기

인과 그래프모델에서는 종속성의 흐름을 파악하는 것이 매우 중요하다. 이를 식별하는 것은 인과성의 파악의 매우 중요한 것으로, 많이 연습하여 익숙해질 필요가 있다. 그런데, 이러한 종속성 흐름을 파이썬 라이브러리인 NetworkX로 쉽게 쿼리 할 수 있다. 그 방법에 대해 알아보도록 하자.

 

NetworkX 소개

NetworkX는 복잡한 네트워크의 구조, 역학 및 기능을 생성하고 조작하며 연구하기 위한 Python 패키지이다. 이 소프트웨어는 그래프(Graph), 유향 그래프(Digraph) 및 다중 그래프(Multigraph)를 위한 데이터 구조를 제공하며, 다양한 표준 그래프 알고리즘, 네트워크 구조 및 분석 측정 기능을 갖추고 있다.

 

또한 NetworkX는 고전 그래프, 임의 그래프 및 합성 네트워크 생성을 위한 제너레이터(generator)를 지원하며, 노드는 텍스트, 이미지, XML 기록 등 무엇이든 될 수 있고 엣지는 가중치, 시계열 등의 임의 데이터를 가질 수 있다.

 

NetworkX는 3-clause BSD 라이선스를 따르는 오픈 소스 소프트웨어로, 90% 이상의 코드 커버리지로 잘 테스트되어 있다. 파이썬의 빠른 프로토타이핑, 교육의 용이성, 멀티 플랫폼 지원 등 추가적인 이점을 제공한다.

 

더욱 자세한 내용은 공식 문서를 참고하도록 하자.

 

NetworkX — NetworkX documentation

 

종속성 쿼리하기

그래프 예시를 하나 살펴보도록 하자.

import graphviz as gr

g_complex = gr.Digraph(graph_attr={'rankdir':'LR'})

g_complex.edge('D','A')
g_complex.edge('A','G')
g_complex.edge('C','A')
g_complex.edge('C','B')
g_complex.edge('B','E')
g_complex.edge('F','E')

g_complex

 

이 그래프에서 우리는 사슬 구조, 분기 구조, 그리고 충돌 구조까지 세 가지 주요 구조를 모두 볼 수 있다. 앞선 게시글에서 각 구조에서 종속 여부를 파악하는 방법에 대해 다뤘으므로, 이를 잘 공부했다면 다음과 같은 질문에 답할 수 있어야 한다.

 

1. 노드 $D$와 $G$는 종속인가? $A$가 주어진 상황에서는 어떤가? (사슬 구조)
2. $A$와 $B$는 종속인가? $C$가 주어진 경우는 어떤가? (분기 구조)
3. $B$와 $F$는 종속인가? $E$가 주어진 경우는 어떤가? (충돌 구조)

 

그리고 이와 더불어 좀더 심화된 질문 또한 존재할 수 있다.

4. $G$와 $F$는 종속인가? $E$가 주어진 경우에 둘 사이 관계에 차이가 생기는가?

 

이처럼 인과 그래프모델에서 종속성 판단의 대상이 되는 조합은 다양하게 존재할 수 있으며 이러한 종속성 질문에 대한 답을 내려보는 것은 인과성의 파악에 중요하다. 하지만 매번 일일히 계산해 보고 판단하기에는 어려움이 있으며 이를 자동으로 수행할 수 있는 패키지를 사용하는 것은 실무적으로 중요할 수 있다. 이제 그 방법에 대해 알아보자.

 

NetworkX 그래프 생성하기

그래프를 다루는 라이브러리인 NetworkX는 다양한 그래프 관련 알고리즘을 제공한다. 우리가 쿼리 하고자 하는 그래프를 NetworkX의 Digraph 함수에 넣음으로써 이러한 알고리즘들을 사용할 수 있다.

import networkx as nx

model = nx.DiGraph([
('C','A'),
('C','B'),
('D','A'),
('B','E'),
('F','E'),
('A','G'),
])

 

이제 인과 그래프모델을 만들었으니 이 모델로 위 질문들에 대한 답을 도출해보도록 하자. 앞서 사슬 구조에 대해 알아볼 때 살펴보았듯이, 노드 $D$와 $A$는 기본적으로 종속이며, 매개자 $A$가 조건부로 설정되었을 때 독립이 된다. 조건부를 설정하고 싶지 않다면 `is_d_seperator()` 함수의 `z` 파라미터를 empty set으로 설정하면 된다. 

print('노드 D와 G는 종속인가?')
print(not(nx.is_d_separator(model,x={'G'},y={'D'},z=set())))
print('A가 주어질 때, 노드 D와 G는 종속인가?')
print(not(nx.is_d_separator(model,x={'G'},y={'D'},z={'A'})))

 

각각의 질문에 대한 답은 Boolean type으로 나오며, 독립인지를 나타내는 `is_d_seperator()`를 `not()`으로 감쌌으므로 첫 번째 질문에 대한 답은 `True`, 두 번째 질문에 대한 답은 `False`가 나오게 된다.

 

마찬가지로, 다른 질문에 대해서도 쿼리를 진행해볼 수 있다.

print('노드 A와 B는 종속인가?')
print(not(nx.is_d_separator(model,x=('A'),y=('B'),z=set())))
print('C가 주어질 때, 노드 A와 B는 종속인가?')
print(not(nx.is_d_separator(model,x=('A'),y=('B'),z={'C'})))

print('노드 B와 F는 종속인가?')
print(not(nx.is_d_separator(model,x=('B'),y=('F'),z=set())))
print('E가 주어질 때, 노드 B와 F는 종속인가?')
print(not(nx.is_d_separator(model,x=('B'),y=('F'),z={'E'})))