[Algorithms] Network Analysis Metrics: Eccentricity, Katz Centrality and Closeness Vitality

Network Analysis Metrics: Eccentricity, Katz Centrality and Closeness Vitality

포스트 난이도: HOO_Senior

---

# Eccentricity

Eccentricity는 노드와 네트워크상의 다른 노드사이의 가장 큰 거리를 계산하는 네트워크 분석 알고리즘에 해당한다. 한마디로 네트워크 상에서 노드끼리의 가장 먼 거리를 측정해 낸다. 예를 들어서 테마파크나 놀이동산에 놀러 온 사람들이 걸어가는 경로를 생각해 보자. Eccentricity는 공원에서 가장 멀리 떨어진 곳에 있는 놀이기구에 가기 위해 누가 가장 멀리 걸어가야 하는지를 측정하는 것과 같다. 바이킹과 롤러코스터를 타러 가려고 하는데 바이킹을 타고나니 롤러코스터가 바이킹 위치에서 가장 먼 위치에 존재하고 있을 때의 경로를 나타내는 게 바로 Eccentricity인 셈이다. 따라서 Eccentricity가 높은 노드는 시스템의 가장 먼 노드로부터 가장 멀리 떨어져 있으므로 Eccentricity가 가장 높은 지점이 된다.

---

# Katz Centrality

Katz Centrality는 다른 노드를 경유하는 노드 쌍 사이의 총 보행 수를 고려하여 네트워크 내에서 노드의 영향력을 측정하며 (또는 직접적으로도 가능하다) , 더 짧은 경로에 더 많은 가중치를 부여한다. 먼 노드의 기여를 약화시키는 요인을 포함함으로써 고유 벡터 중심성의 개념을 확장한다. 예를 들어, 우리의 지인 또는 친구들의 관계(=인맥)를 Web으로 구현한다고 했을때, Katz Centrality은 가까운 친구들뿐만 아니라 친구들의 친구들까지 연결되어 짧은 경로에 더 많은 가중치를 부여해 가면서 중심성의 개념을 확장한다. 그렇기에  Katz Centrality의 관점에서 인맥을 정의했을 때 마치 Web의 가장자리까지 진동을 느끼며 바로 중심에 있는 거미와 같이 느껴질 수 있다는 것이다. 아래의 plot처럼 Katz Centrality를 통해서 사람들 간의 관계나 인맥에 대해서 정의하고 산출해 내면 본인이 얼마나 영향력이 있는지 알 수 있는 재미있는 결과를 살펴볼 수 있다.

---

# Closeness Vitality

Closeness Vitality는 특정 노드를 네트워크에서 제거할 때 모든 노드 쌍 사이의 거리의 합의 변화를 측정한다. 기본적으로 노드가 네트워크의 전체 근접도에 미치는 영향을 정량화한다. 예를 들어서 서울에서 차량 통행량이 가장 많은 회전교차로가 갑자기 공사를 위해 일시적으로 폐쇄되었다고 가정해보자. 이때 Closeness Vitality 네트워크 분석을 통해서 사람들이 회전교차로를 통해 지름길로 갈 수 없기 때문에 임의의 A 지점에서 B 지점으로 가는 데 얼마나 많은 여분의 시간을 소비하는지를 측정할 수 있다.

---

# Results

앞서서 Eccentricity, Katz Centrality 그리고 Closeness Vitality에 대해서 간단하게 리뷰를 해보았다. 아래의 Figure 1은 글쓴이가 가볍게 예시로 만들어본 각각의 네트워크 분석 알고리즘들을 나타내는 Data visualization이다. 색깔에 따라서 정도의 차이를 구분해 두었기에 세 종류의 네트워크 분석들을 비교하기 용이하다.

Figure 1. Network analysis metrics: Eccentricity, Katz Centrality and Closeness Vitality.

 

---

# Code for Figure 1

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
#Reference
#https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.vitality.closeness_vitality.html
#https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.distance_measures.eccentricity.html
#https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.katz_centrality.html

# Create a graph
G = nx.karate_club_graph()

# Compute metrics
eccentricity = nx.eccentricity(G)
katz_centrality = nx.katz_centrality(G, alpha=0.1, beta=1.0)
closeness_vitality = nx.closeness_vitality(G)

# Create a layout for our nodes 
layout = nx.spring_layout(G)

# Plotting without normalization and with different color maps for each metric
plt.figure(figsize=(18, 6))

# Eccentricity
plt.subplot(1, 3, 1)
ecc_values = list(eccentricity.values())
nx.draw_networkx(G, pos=layout, node_color=ecc_values, with_labels=True, cmap=plt.cm.viridis)
plt.title('Eccentricity')
plt.colorbar(plt.cm.ScalarMappable(norm=plt.Normalize(vmin=min(ecc_values), vmax=max(ecc_values)), cmap=plt.cm.viridis), ax=plt.gca())

# Katz Centrality
plt.subplot(1, 3, 2)
katz_values = list(katz_centrality.values())
nx.draw_networkx(G, pos=layout, node_color=katz_values, with_labels=True, cmap=plt.cm.plasma)
plt.title('Katz Centrality')
plt.colorbar(plt.cm.ScalarMappable(norm=plt.Normalize(vmin=min(katz_values), vmax=max(katz_values)), cmap=plt.cm.plasma), ax=plt.gca())

# Closeness Vitality
plt.subplot(1, 3, 3)
vitality_values = list(closeness_vitality.values())
# Adjust vitality values to remove negative infinity
vitality_values = [max(val, min(vitality_values)) if val == float('-inf') else val for val in vitality_values]
nx.draw_networkx(G, pos=layout, node_color=vitality_values, with_labels=True, cmap=plt.cm.inferno)
plt.title('Closeness Vitality')
plt.colorbar(plt.cm.ScalarMappable(norm=plt.Normalize(vmin=min(vitality_values), vmax=max(vitality_values)), cmap=plt.cm.inferno), ax=plt.gca())

plt.show()

---

# Github

https://github.com/WhoisHOO/HOOAI/blob/main/Data%20Science/network_analysis_metrics_1

---

# Refereces

• https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.vitality.closeness_vitality.html
• https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.distance_measures.eccentricity.html
• https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.katz_centrality.html

---