[NetwrokX] 그래프 연결성분(연결요소, Connected Components)

 

그래프 연결성분(연결요소)이란 쉽게 말해서 서로 분리되어 있는 그래프를 뜻합니다.

위의 (A~O)그래프에서는 3개의 연결성분이 있는거죠.

 

연결성분의 조건

• 연결성분 안의 모든 노드들은 동일한 성분 내의 다른 노드와 연결되어 있어야한다.
• 연결성분 밖에 있는 노드와 연결되면 안된다.

 

즉,  소외 되는 노드가 없으면서도 외부와의 접촉도 없는,

일종의 섬같은 성분을 연결성분이라고 부르는 겁니다.

 

위의 조건에 따라, 

1번 : {A,E,F,G}는 연결성분이 아닙니다. (서로 분리되어 있으므로)

2번 : {K,L,O}는 연결성분이 아닙니다. (외부의 노드 M,L과 연결되어있으므로)

3번 : 오로지 {A,B,C,D,E}, {E,F,G,H,I}, {J,K,L,M,N,O}만 위 그래프의 연결성분입니다.

 

 

무방향 그래프 연결성분 확인하기

연결성분 개수 확인하기

nx.number_connected_components(G)  # 3

 

연결성분 내용 확인하기

sorted(nx.connected_components(G))
# [{"A","B","C","D","E"}, {"F","G","H","I","J"}, {"K","L","M","N","O"}]

 

특정 노드가 속한 연결성분 확인하기

nx.node_connected_component(G, "M")
# {"K","L","M","N","O"}