[NetworkX] 네트워크 견고성(Robustness in Networks)

네트워크 견고성 (Robustness in Networks)

The ability of a network to maintain its general structural properties whet it faces failures or attacks
출처 : Applied Social Network Analysis in Python(by Daniel Romero)

• 네트워크 견고성: 네트워크의 구조를 유지하는 능력, 연결성을 유지하는 능력

네트워크 견고성이란,

네트워크가 고장나거나 공격을 받더라도 연결성을 잃지 않는 능력이라는 뜻입니다.

 

즉, 노드나 엣지가 제거되더라도 네트워크가 제 기능을 할 수 있느냐는 뜻이죠.

 

인천공항에 사고가 생기면 김포공항으로 회항하면 되지만(견고성 확보)

제주공항에 사고가 생기면 제주도에는 못들어 가는 경우로(견고성 부족) 예시를 들 수 있겠습니다.

 

 

NetworkX 실습

1. node_connectivity(G), minimum_node_cut(G)

import networkx as nx

edges = [('A','E'),('A','B'),('A','N'),('A','G'),('A','C'),
         ('B','C'),('B','D'),('B','E'),('C','D'),('C','E'),
         ('D','E'),('G','F'),('G','H'),('G','I'),('G','J'),
         ('F','I'),('F','J'),('H','I'),('I','J'),('J','O'),
         ('O','N'),('O','K'),('O','L'),('N','L'),('K','L'),
         ('K','M'),('L','M')]

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

위와 같은 그래프가 있다고 해봅시다.

 

그래프G의 연결성(connectivity)을 제거하려면 몇개의 "노드"를 없애면 될까요?

nx.node_connectivity(G)를 이용하면 알 수 있습니다.

nx.node_connectivity(G)
# 1

그럼 어떤 노드를 없애야 할까요?

nx.minimum_node_cut(G)를 이용하면 알 수 있습니다.

 

nx.minimum_node_cut(G)
# {'A'}

G.remove_node('A')를 하니 그래프가 둘로 쪼개졌습니다.

2. node_connectivity(G), minimum_node_cut(G)

위와 동일한 그래프로 진행합니다.

 

그래프G의 연결성(connectivity)을 제거하려면 몇개의 "엣지"를 없애면 될까요?

nx.edge_connectivity(G)를 이용하면 알 수 있습니다.

nx.edge_connectivity(G)
# 2

그럼 어떤 엣지를 없애야 할까요?

nx.minimum_edge_cut(G)를 이용하면 알 수 있습니다.

nx.minimum_edge_cut(G)
# {('G', 'A'), ('N', 'A')}

G.remove_edges_from([('G', 'A'), ('N', 'A')]) 결과, 둘로 나뉘었습니다.