📂그래프이론

네트워크 이론에서의 매개 중심성

정의 ¹

스트레스 중심성

네트워크 $\left( V, E \right)$ 에서 두 노드 $s,t \in V$ 를 잇는 최단 거리인 패스의 갯수를 $\sigma_{st} = \sigma_{ts}$ 라 하고, 특히 $s,t$ 를 잇는 패스 중 또 다른 노드 $v \in V$ 를 포함하는 패스의 갯수를 $\sigma_{st} (v)$ 와 같이 나타내자. 다음과 같이 정의된 $C_{S} : V \to \mathbb{Z}$ 를 노드 $v$ 의 스트레스 중심성^{stress Centrality}이라 한다. $$ C_{S} (v) := \sum_{s \ne v \ne t \in V} \sigma_{st} (v) $$

매개중심성

다음과 같이 정의된 $C_{S} : V \to \mathbb{R}$ 를 노드 $v$ 의 매개 중심성^{betweenness Centrality}이라 한다. $$ C_{B} (v) := \sum_{s \ne v \ne t \in V} {{ \sigma_{st} (v) } \over { \sigma_{st} }} $$

설명

$\sigma_{st} (v)$

$\sigma_{st}$ 의 정의를 잘 읽어보면 $s,t$ 사이의 최단거리 $d(s,t) = d(t,s)$ 가 아니라 그렇게 최단거리가 되는 경로의 수로, 모든 $v \in V$ 에 대해 $\sigma_{vv} = 1$ 이고 그래프의 거리 함수 $d$ 에 대해 $\sigma_{st} (v)$ 는 다음과 같다. $$ \sigma_{st} (v) = \begin{cases} 0 & , \text{if } d \left( s , t \right) < d \left( s , v \right) + d \left( v , t \right) \\ \sigma_{sv} \cdot \sigma_{vt} & , \text{otherwise} \end{cases} $$

직관적인 의미

$$ C_{S} (v) = \sum_{s \ne v \ne t \in V} \sigma_{st} (v) \\ C_{B} (v) = \sum_{s \ne v \ne t \in V} {{ \sigma_{st} (v) } \over { \sigma_{st} }} $$ 매개 중심성은 본질적으로 스트레스 중심성과 같은 개념으로, 자연스럽게 교통/통신의 측면에서 해당 노드가 얼마나 중요한지를 나타내게 된다. 스트레스 중심성과는 달리 $s,t$ 마다 $\sigma_{st}$ 를 나눠주어서 해당 노드가 조금 더 적절하게 평가되도록 수정되었다.

같이보기

네트워크의 여러가지 중심성

• 🔒(24/02/08) 차수 중심성
• 🔒(24/02/16) 매개 중심성
  • 🔒(24/02/12) 스트레스 중심성
• 근접 중심성
• 고유벡터 중심성