[NetworkX] 양분그래프, Bipartite Graph (파이썬 네트워크 분석 9)

Bipartite Graph(양분그래프, 이분그래프)

요약

• 두개의 노드 집합으로 나누어지는 그래프
• 모든 엣지는 서로 다른 집합에 속한 노드끼리의 연결만으로 이루어진 그래프
• 즉, 같은 집합에 속한 노드끼리 엣지가 연결된 경우가 전혀 없는 그래프
• from networkx.algorithms import bipartite 로 사용 가능

 

농구팬-농구팀 양분그래프

양분그래프란, 노드들이 두개의 집합으로 나누어지는 그래프를 의미합니다.

위의 사진 예시를 보죠.

 

두개의 집단이 있습니다.

오른쪽(R) 집단에는 농구팀 노드들이, 왼쪽(L) 집단에는 팬들이 있습니다.

모든 엣지는 [팬-팀(L-R)] 관계를 나타냅니다.

 

여기서 중요한건, L-R 관계가 아닌 엣지는 하나도 없다는 것입니다.

L-L 관계와 R-R 관계인 엣지가 하나도 없습니다.

팬1이 팬3의 팬이 될 수 없고, 삼성라이온즈가 한화이글스의 팬이 될 수는 없습니다. (농구팀은 제가 몰라서...ㅋㅋㅋ)

 

이렇게 노드가 두개의 집단으로 양분되고, 같은 집단 안에서는 노드간 연결이 없는 그래프를 양분그래프, Bipartite Graph라고 부릅니다.

 

그래프 생성

위의 예시 사진과 같은 그래프를 만들어봅시다.

import networkx as nx

G = nx.Graph()

# 노드 추가 + 양분bipartite 집단 정의
G.add_nodes_from(['A','B','C','D','E'], bipartite=0)
G.add_nodes_from([1,2,3,4], bipartite=1)

# 엣지 추가
G.add_edges_from([('A',1),('B',1),('C',1),('C',3),('D',2),('E',3),('E',4)])

생성 방식은 기본적인 그래프 생성과 똑같습니다.

노드를 정의할 때 bipartite를 추가로 정의해 주었다는 것이 핵심 포인트입니다.

 

양분그래프인지 검토하기

from networkx.algorithms import bipartite

bipartite.is_bipartite(G)
# 출력: True

위의 예시는 양분그래프였기 때문에 당연히 True가 출력됩니다.

그런데 여기서 엣지를 이상한곳에 하나 더 추가해보면 어떨까요?

이러면 더이상 bipartite가 아닙니다.

# 같은 집단에 속한 노드끼리 엣지 연결
G.add_edge('A','B')

# 결과확인
bipartite.is_bipartite(G)
# 출력: False

같은 집단끼리는 엣지연결되면 안된다는 것이 bipartite graph의 조건이기 때문에,

이 그래프는 더이상 bipartite graph가 아닙니다.

# 그래프 원상복구 시켜주기
G.remove_edge('A','B')

 

Bipartite Graph의 set(집단) 확인하기

1) 먼저 주어진 노드집단이 하나의 set인지를 확인해볼 수 있습니다.

# 경우1
X = set([1,2,3,4])
bipartite.is_bipartite_node_set(G,X)
# True

# 경우2
X = set(['A','B','C','D','E'])
bipartite.is_bipartite_node_set(G,X)
# True

# 경우3
X = set([1,2,3,4,'A'])
bipartite.is_bipartite_node_set(G,X)
# False

# 경우4
X = set([1,2,3])
bipartite.is_bipartite_node_set(G,X)
# False

여기서 중요한 점은,

정확한 세트인 경우에만 True를 출력한다는 점입니다. (경우1, 경우2)

서로 다른 세트의 노드가 섞여있거나(경우3)

온전하지 않은 경우(경우4)에는 False를 출력합니다.

 

즉, is_bipartite_node_set은

정말 양 집단(set)중 하나에 정확히 해당하는 경우에만 True를 출력합니다.

 

2) 그래프 G의 전체 모습을 모르는 경우엔 bipartite set이 무엇인지 직접적으로 물어볼 수 있습니다.

bipartite.sets(G)로 확인할 수 있습니다.

bipartite.sets(G)

---------------------------------------------------------------------------
AmbiguousSolution                         Traceback (most recent call last)
<ipython-input-24-f2618f01e6e8> in <module>
----> 1 bipartite.sets(G)

/usr/local/lib/python3.7/dist-packages/networkx/algorithms/bipartite/basic.py in sets(G, top_nodes)
    199         if not is_connected(G):
    200             msg = "Disconnected graph: Ambiguous solution for bipartite sets."
--> 201             raise nx.AmbiguousSolution(msg)
    202         c = color(G)
    203         X = {n for n, is_top in c.items() if is_top}

AmbiguousSolution: Disconnected graph: Ambiguous solution for bipartite sets.

어라, 여기서 에러가 발생합니다.

AmbiguousSolution: Disconnected graph: Ambiguous solution for bipartite sets.

 

이런 에러는 현재의 그래프G가 Connected Graph가 아니기 때문입니다.

이렇게 분리될 수 있기 때문에 Disconnected Graph입니다.

현재의 그래프G는 위의 사진처럼 두개의 그래프로 분리될 수 있습니다.

분리될 수 있다면 Disconnected Graph입니다.

 

때문에 공식문서에서는 bipartite.sets(G)를 사용하기 전, 그래프G가 완전히 연결된 그래프인지를 먼저 확인하고 있습니다.

https://networkx.org/documentation/stable/reference/algorithms/bipartite.html

# 공식문서 중 일부
nx.is_connected(G)  # True
bottom_nodes, top_nodes = bipartite.sets(G)

우리는 실습을 해야하니, D노드와 3노드를 임의로 연결해주겠습니다.

D-3 엣지를 추가해봅시다

nx.is_connected(G)  # False

G.add_edge('D',3)
nx.is_connected(G)  # True

bipartite.sets(G)
# ({'A', 'B', 'C', 'D', 'E'}, {1, 2, 3, 4})

이제 양쪽 세트를 잘 출력해줍니다.