[NetworkX] 그래프를 거리(length)로 설명하는 방법(평균거리, 지름, 반지름, 둘레, 이심률)

그래프G를 간추려서 수치로 설명하는 방법은 여러가지가 있습니다.

 

Average distance: 모든 노드 간 거리의 평균

nx.average_shortest_path_length(G)

위와 같은 그래프가 있다고 할 때, A로부터 다른 노드들 까지의 거리는 다음과 같습니다.

nx.shortest_path_length(G,'A')

# 결과
{'A': 0, 'B': 1, 'K': 1, 'C': 2, 'F': 3, 'E': 3, 'G': 4, 'H': 4, 'I': 4, 'D': 4, 'J': 5}

A~J까지의 모든 노드들에 대해서 위의 방법을 실행하고, 그 평균을 내면되지만,

굳이 직접 평균을 계산할  필요는 없습니다.

nx.average_shortest_path_length(G)
# 2.5272727272727273

위의 값과 똑같을 겁니다. 

 

 

Diameter 지름: 가장 거리가 긴 path의 길이

nx.diameter(G)

우리가 일반적으로 알고있는 지름(원의 지름)의 개념과는 좀 다릅니다.

그래프에서의 지름의 개념은 다음과 같습니다.

• maximum distance between any pair of nodes
• = 그래프 G 내, 노드 간 거리의 최대값

nx.diameter(G)
# 5

 

 

Eccentricity 이심률: 가장 거리가 긴 path의 길이

nx.eccentricity(G)

한 노드가 가지는 다른 노드와의 최대 거리

• the largest distnace between n and all other nodes
• 한 노드와 다른 노드들 사이의 최대 거리

nx.eccentricity(G)

# 결과
{'A': 5, 'B': 4, 'K': 5, 'C': 3, 'E': 3, 'F': 3, 'D': 4, 'H': 4, 'G': 4, 'I': 4, 'J': 5}

사실 위의 지름diameter는 이심률 값 중 가장 큰 값(5) 였습니다.

 

 

Radius 반지름: 가장 거리가 긴 path의 길이

nx.radius(G)

지름과는 반대로, 반지름은 이심률 값 중 가장 작은 값입니다.

• 한 노드와 다른 노드들 사이의 최대 거리가 가장 짧은 값
• = 이심률 중 가장 작은 값

nx.radius(G)
# 3

 

 

Periphery 둘레: 이심률이 지름인 노드들의 집합

Center 중앙: 이심률이 반지름인 노드들의 집합

nx.periphery(G), nx.center(G)

둘레Periphery는 그래프 G의 가장 끝자락에 있는 노드들의 집합이라고 생각하면 편합니다.

이심률이 가장 크다는건, 그만큼 가장자리에 있다는 뜻이니까요.

중앙Center는 중앙에 있는 노드들이라고 생각하면 됩니다.

• the set of nodes that have eccentricity equal to the diameter
• 둘레: (이심률=지름)인 노드들의 집합
• 중앙: (이심률=반지름)인 노드들의 집합

nx.periphery(G)
# ['A', 'K', 'J']

nx.center(G)
# ['C', 'E', 'F']

둘레(좌), 중앙(우)