📂그래프이론

네트워크 이론에서의 고유벡터 중심성

정의 ¹

네트워크 $\left( V , E \right)$의 인접행렬 $A$ 의 스펙트럴 래디어스 $\lambda_{1}$ 에 대응되는 고유벡터 $\mathbf{v}_{1}$ 의 $i$번째 성분을 $i$번째 노드 $v_{i}$ 의 고유벡터 중심성^{eigenvector Centrality}라 한다.

설명

수식에서 직관적인 의미를 바로 파악할 수 있는 매개 중심성이나 근접 중심성 등과 달리 아이겐벡터 중심성은 수학을 전공하지 않으면 정의을 읽는 것부터가 어려울 수 있다.

직관적인 의미

유도과정을 봐야 이해할 수 있는데, 쉽게 말해 해당 노드가 네트워크에서 가지고 있는 영향력을 의미한다. 이 영향력이라는―어떻게 보면 모호한 힘은 단순히 인접한 노드들과의 관계만으로는 설명할 수 없고, 차수 중심성과 같은 척도의 한계를 뛰어넘기 위해 고유벡터라는 어려운 개념이 필요해진다.

유도

모든 노드 $v_{i} \in V$ 에 대해 어떤 중심성 $x_{i}$ 가 대응된다고 하자. 아직은 이 중심성이 어떻게 계산되는지 모르겠지만, 이 중심성은 주변의 중심성이 클수록 고평가되는 성질을 가진다고 가정하자. 이는 방송계에서 연예인들이 일을 할 때 완전히 랜덤하고 뜬금없는 조합을 갖추지 않고 어느정도 급과 분야가 맞는 사람들끼리 섭외되거나 학계에서 같이 논문을 쓸 때 비슷한 현상이 일어나는 것을 반영하려는 의도가 있다. 그러면 $x_{i}$ 는 다음과 같이 인접한 노드들 $\left\{ v_{j} \right\}$ 들의 $\left\{ x_{j} \right\}$ 의 합으로 나타낼 수 있을 것이다. $$ x_{i} = \sum_{j} A_{ij} x_{j} $$ 그러나 $x_{i}$ 자체가 변하는 순간 $\left\{ x_{j} \right\}$ 도 변할 수 있다보니 이렇게 계산하는 건 문제가 있어보인다. 당장은 반복 횟수에 대한 변수 $t$ 를 추가해서 $$ x_{i} (t+1) = \sum_{j} A_{ij} x_{j} (t) $$ 와 같이 적어보자. 이는 $\mathbf{x} := \left( x_{1} , \cdots , x_{n} \right)$ 에 대해 곧 $$ \mathbf{x} (t+1) = A \mathbf{x} (t) $$ 와 같은 행렬 표현이 가능해지며 정확히 다음과 같은 솔루션을 가지는 동역학계 그 자체다. $$ \mathbf{x} (t) = A^{t} \mathbf{x} (0) $$ 이 시스템은 $\mathbf{x} (0)$ 에 종속된 결정계^{deterministic system}다. 우리가 구하려는 중심성 벡터 $\mathbf{x} (t)$ 의 초기점 $\mathbf{x} (0)$ 이 무엇이어야 한다는 이유는 없으나, 어떤 상수의 집합 $\left\{ c_{j} \right\} \subset \mathbb{R}$ 에 대해 다음과 같이 $A$ 의 고유벡터 $\left\{ \mathbf{v}_{j} \right\}$ 의 선형결합으로 두자. $$ \mathbf{x} (0) = c_{1} \mathbf{v}_{1} + \cdots + c_{n} \mathbf{v}_{n} = \sum_{j=1}^{n} c_{j} \mathbf{v}_{j} $$ 여기서 고유벡터의 집합 $\left\{ \mathbf{v}_{j} \right\}$ 은 $A$ 의 고유값이 절대값 크기 순으로 정렬된 $\left\{ \lambda_{j} \right\}$ 와 동일한 인덱스 $j$ 를 공유한다고 하자. 그러면 $j$번째 고유벡터 $\mathbf{v}_{j}$ 에 대해 고유값은 $$ A \mathbf{v}_{j} = \lambda_{j} \mathbf{v}_{j} \implies A^{t} \mathbf{v}_{j} = \lambda_{j}^{t} \mathbf{v}_{j} $$ 를 만족하며, 따라서 $$ \begin{align*} \mathbf{x} (t) =& A^{t} \mathbf{x} (0) \\ =& A^{t} \sum_{j=1}^{n} c_{j} \mathbf{v}_{j} \\ =& \sum_{j=1}^{n} c_{j} A^{t} \mathbf{v}_{j} \\ =& \sum_{j=1}^{n} c_{j} \lambda_{j}^{t} \mathbf{v}_{j} \\ =& \lambda_{1}^{t} \sum_{j=1}^{n} c_{j} \left( {{ \lambda_{j} } \over { \lambda_{1} }} \right) ^{t} \mathbf{v}_{j} \end{align*} $$ 한편 아이겐밸류 $\left\{ \lambda_{j} \right\}$ 들은 절대값 크기 순으로 정렬되어있으므로 $j \ne 1$ 에 대해 $\left( \lambda_{j} / \lambda_{1} \right) < 1$ 이고, 충분히 큰 $t$ 에서 다음의 근사^{approximation}식이 성립한다. $$ \begin{align*} \mathbf{x} (t) =& \lambda_{1}^{t} c_{1} \left( {{ \lambda_{1} } \over { \lambda_{1} }} \right) ^{t} \mathbf{v}_{1} + \lambda_{1}^{t} c_{2} \left( {{ \lambda_{2} } \over { \lambda_{1} }} \right) ^{t} \mathbf{v}_{2} + \cdots + \lambda_{1}^{t} c_{n} \left( {{ \lambda_{n} } \over { \lambda_{1} }} \right) ^{t} \mathbf{v}_{n} \\ \approx & \lambda_{1}^{t} c_{1} \mathbf{v}_{1} + 0 + \cdots + 0 \end{align*} $$ 여기서 $\lambda_{1}^{t}$ 와 $c_{1}$ 이 무엇이든 중요한 것은 $t$번의 반복 끝에 얻을 $\mathbf{x} (t)$ 가 결국 $\lambda_{1}$ 에 대응되는 $\mathbf{v}_{1}$ 에 비례한다는 것, 즉 $$ \begin{bmatrix} x_{1} \\ \vdots \\ x_{n} \end{bmatrix} = \mathbf{x} (t) \sim \mathbf{v}_{1} $$ 이라는 것이다. 이에 우리는 ‘$t$번만큼 반복한다’는 과정을 생략하고 그냥 $\mathbf{v}_{1}$ 의 $i$번째 성분을 처음 계산하고자 했던 노드 $v_{i}$ 의 중심성 $x_{i}$ 로 쓰는 것이다.

■

같이보기

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

• 차수 중심성
• 매개 중심성
  • 스트레스 중심성
• 근접 중심성
• 고유벡터 중심성