[네트워크이론] 네트워크 중심성 - link를 통해 전달되는 것들

 다양한 네트워크 중심성 중 "link를 통한 전달되는 것들"의 관점에서 정의할 수 있는 중심성들에 대해서 정리해 보았다.

---

Degree centrality - 연결 중심성

 연결중심성은 쉽게 말하면 이웃 node의 개수이지만 굳이 더 의미를 찾아보자면, 네트워크 상에서 임의로 움직이는 행위자가 한 node에 머물 확률이기도 하다. 

 

네트워크 상에서 random walk 행위자가 시점 t에서 각 node에 있을 확률을 벡터로 나타내어 p(t)라고 했을 때, 그 다음 스탭의 확률은 다음과 같다

 

$\mathbf{p}(t+1) = \mathbf{A} \mathbf{D} ^{-1} \mathbf{p}(t) $

 

 여기서 A는 인접행렬, D는 degree를 주대각성분으로 갖는 행렬이다. 인접행렬은 한 node로 부터 주변 node로의 정보를 갖고 있고, 이 때 임의의 방향으로 이동하기 때문에 확률을 degree로 나눠주는 것이다.

 이를 무한 번 반복하여, $\mathbf{p}(t)$가 수렴했을 때 $\mathbf{p}$는 다음과 같다.

 

$\mathbf{p} = \mathbf{A}\mathbf{D}^{-1}\mathbf{p}$

 

 이를 변형하면,

 

$(\mathbf{I} - \mathbf{A}\mathbf{D}^{-1})\mathbf{p} = (\mathbf{D}-\mathbf{A})\mathbf{D}^{-1}\mathbf{p} = \mathbf{L}\mathbf{D}^{-1}\mathbf{p} = 0$

 

 이 때 $\mathbf{L}$은 Graph Laplacian이라고 불린다. (인접 공간과의 차이에 대한 관계를 묘사하는 행렬로, 확산법칙과 개념적으로 깊은 관계를 갖고 있다.)

 

 Graph Laplacian은 $\mathbf{D} - \mathbf{A}$ 이므로, 벡터 $\mathbf{1}$을 곱해주면 0이된다.  ( $k_{i} \cdot 1 - \sum_{j} 1 = 0 $ )

 

 고로, 

$\mathbf{D}^{-1}\mathbf{p} = c\mathbf{1}$

$\mathbf{p} = c\mathbf{D}\mathbf{1}$

이 되고, node i 에 random walk 행위자가 머물 확률 $p_{i}$는

 

$p_{i} = ck_{i}$

즉, degree에 비례한다.

 

결론, degree centrality는 네트워크 상 임의로 행동하는 행위자가 머물 확률에 비례한다.

 

---

Eigenvector centrality - 고유벡터 중심성

 Eigenvector centrality는 주변 node의 중심성 까지 고려한다. Network 를 통해 각 node의 중요도를 무한히 전파시켰을 때, 수렴하게 되는 중요도의 양의 비율을 말한다.

 Degree centrality와 다른 점은 확률이 아니므로, link상에서 전파할 때 degree로 중요성을 나눠주지 않는다는 점이다. 즉, 한 node의 중요도는 그대로 주변 node의 중요도에 반영된다.

 Bipartite network (동일 layer간 connection을 갖지 않는 두 layer간의 network) 또는 link의 weight이 음의 값을 갖지 않는다면, 전달되는 양은 횟수를 거치면서 수렴하기 때문에, 대부분의 network에서 정의 가능하다.

 

 각 node의 중요도를 $x_{i}$라고 했을 때, 네트워크 상 전파되는 중요도 벡터 $\mathbf{x}$는 다음과 같다.

 

$\mathbf{x}(t+1) = \frac{1}{\lambda}\mathbf{A}\mathbf{x}(t)$

 

 여기서, $\lambda$는 비례계수. $\mathbf{x}$가 수렴하면,

 

$\mathbf{x} = \frac{1}{\lambda}\mathbf{A}\mathbf{x}$

 

$\lambda\mathbf{x} = \mathbf{A}\mathbf{x}$

 

 $\lambda$는 $\mathbf{A}$의 고유값, $\mathbf{x}$는 $\mathbf{A}$의 고유벡터다. 여기서, $\mathbf{x}$가 고유벡터 중심성이다. 

 

 당연한 말이지만 특징으로는 한 node i의 고유 벡터 중심성은 주변 node의 고유벡터 중심성을 더한 값을 고유값으로 나눠준 값이다.

 

 $x_{i} = \frac{1}{\lambda}\sum_{j=1}^{n} a_{ij}x_{j}$

 

 결론은 $\lambda$의 비율은 고정이므로, 한 node의 고유벡터 중심성은 주변 node의 고유벡터 중심성의 합이다. 즉, 주변 node의 중심성이 반영된다.

---

Katz centrality

 Katz centrality는 Eigenvector centrality와 거의 동일한데, constant항과 주변 node의 중심성에 계수를 적용해서 eigenvector의 반영 강도를 조정할 수 있다. 

 구체적으로는 다음과 같다.

 

 $x_{i} = \alpha\sum_{j} a_{ij}x_{j} + \beta$

 

 $\alpha$가 주변의 중심성에 곱해지는 계수, $\beta$는 기본적으로 갖는 중요성이다. $\alpha$가 0으로 가면 모든 node는 같은 중심성 $\beta$를 갖게 되고, $\alpha$가 커질 수록 eigenvector 중심성 강도가 높게 반영된다.

---

PageRank centrality

 큰 규모의 network에서 나타날 수 있는 Katz centrality의 약점을 보강한 중심성. Eigenvector centrality를 포함, Katz centarlity의 문제점은 중심성이 그대로 주변 node에게 전파된다는 점인데, 아주 큰 hub 주변의 중심성이 너무 높게 평가되는 약점을 갖는다. 

 PageRank centrality는 중심성이 전파될 때 degree (out)로 나눠줌으로써 이 약점을 보강했고, 인터넷 같이 큰 규모의 네트워크에 대한 중심성으로써 활약했기 때문에 유명해졌다.

 

$x_{i} = \alpha\sum_{j} a_{ij}\frac{x_{j}}{k_{j}^{out}}$

 

 Degree로 나눈다는 점에서, Degree centrality와 Katz centrality의 중간 지점에 위치한 중심성이라고 생각해볼 수 있다. 

---

 지금까지는 거리와 상관 없이 무한히 network 상을 이동하는 것들에 대해 정리해 보았다.  간단히 정리해보면, 다음과 같다.

 

	constant 항 X	constant 항 O
degree로 나눔 X	eigenvector centrality	Katz centrality
degree로 나눔 O	degree centrality	PageRank centrality

 

이제부터는 거리가 멀어질 수록 전달의 감도가 떨어지는 것들에 대해 알아보자.

---

Subgraph centrality

 Subgraph는 한 그래프에 속한 하위 집합 그래프다. Subgraph centrality는 모든 가능한 subgraph에서 각 node의 참여도를 정량화 한다. 쉽게 말하자면, 여기저기 많은 subgraph에 포함될 수록 인싸.

 

 구체적으로는 한 node p로 부터 시작해서 n step만에 다시 node p로 돌아오는 모든 닫힌 loop를 조사하는데, 그 이유는 다시 돌아온다는 것은 하나의 연결된 graph에서 일어날 수 있는 사건이기 때문이다. 즉 닫힌 loop(closed walk)가 하나의 subgraph라는 것이다.

 

한 node p 에서 시작해서 n step 이동 후 node p로 돌아오는 루프의 개수는, 인접행렬 $\mathbf{A}$ 를 n회 곱한 후 갖는 주대각성분의 p항에 해당한다.

 

$\mu_{n}(p) = \mathbf{A}^{n}_{pp}$

 

 이를 모든 가능한 step n에 대해 구하면, 다음과 같다.

 

$C_{p} = c_{0}\mathbf{A}^0_{pp} + c_{1}\mathbf{A}^{1}_{pp} + \cdots = \sum_{l=0}^{\infty} c_{l}\mu_{l}(p)$

 

 여기서 계수 $c_{l}$는 루프의 거리가 짧을 수록 높은 값을 가지도록 정하는데, 이는 루프의 거리가 짧을 수록 작은 subgraph에 참여한 상황을 상정할 수 있고, 이는 상대적으로 해당 node의 중요도가 높아지기 때문에 그렇다.

 

 쉽게 말하면, 작은 subgraph를 많이 가질 수록, 중요도가 높다는 것이다. (여기저기 많은 조합에 참여하기 때문에 인싸)

 

 $c_{l}$는 다음과 같은 조건을 같는다.

(1) 이 값이 수렴하도록 정할 것

(2) 거리 l이 길 수록 중요성이 낮도록 정할 것

(3) 양의 값을 가질 것

 

 이에 해당하는 적합한 계수로 $l!$을 정하는데, 이는 단순히 위의 조건을 만족시킬 뿐 아니라 exponential을 포함한다는 점에서도 의미가 있다. (=이쁘다 & 계산의 용이성)

 

 테일러 시리즈를 이용하면 $e^{x}$는 다음과 같다.

 

 $e^{x} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \cdots$

 

 이는 x를 허수로도 행렬으로도 개념적으로 확장할 수 있다는 점에서 매력적인데, 윗 식에서 정의된 subgraph centrality $C_{p}$는 다음과 같이 표현할 수 있다.

 

 $C_{p} = (e^{\mathbf{A}})_{pp}$

 

 이런 표현 방법을 matrix exponential 이라고 하는데, 인접행렬의 고유값과 고유벡터를 이용해서 값을 구할 수 있다. 먼저, 인접행렬은 다음과 같이 분해할 수 있다.

 

 $\mathbf{A} = \mathbf{U} \mathbf{D} \mathbf{U}^{-1}$

 

 여기서 $\mathbf{U}$는 고유벡터 행렬, $\mathbf{D}$는 고유값을 주대각성분으로 갖는 행렬이다.

 이를 이용하면,

 

 $e^{\mathbf{A}} = \sum_{n=0}^{\infty} \frac{1}{n!}\mathbf{A}^{n} = \sum_{n=0}^{\infty} \frac{1}{n!} \mathbf{U} \mathbf{D}^{n} \mathbf{U}^{-1} = \mathbf{U} (\sum_{n=0}^{\infty} \frac{1}{n!} \mathbf{D}^{n}) \mathbf{U}^{-1}$

 

 가 되는데, 대각행렬의 n승은 각 성분의 n승과 같으므로 따로따로 테일러 시리즈를 적용하면, 

 

 $e^{\mathbf{A}} = \mathbf{U} \mathbf{diag}(e^{\lambda_{1}}, e^{\lambda_{2}}, \cdot) \mathbf{U}^{-1}$

 

 즉, 인접행렬 $\mathbf{A}$의 고유값과 고유벡터로 구할 수 있게 된다.

 

$C_{p} = \sum_{j} \mathbf{\phi_{j}}(p)^{2} e^{\lambda_{j}}$

 

 그리고 이는 subgraph를 많이 가지는 인싸를 정량화 한다. (특히 작은 규모의 subgraph를 많이 가질 수록 더 인싸)

 

---

Communicability

 Communicablity는 subgraph centrality와 방법은 같으나 서로 다른 node를 끝과 끝으로 둔다는 점에서 차이가 있다. Subgraph centrality에서는 node p에서 출발하여 다시 node p로 돌아올 때의 closed walk 가 하나의 subgraph라는 관점으로 그 강도를 정량화 하지만, Communicability는 node p 에서 출발하여 node q 로 가는 모든 루트에 대한 강도를 정량화 한다. 그래서, 이름도 communicability(전달성)다. 

 

node p 에서 node q로의 가장 짧은 거리를 s라고 하고, 이 때 가능한 루트의 개수를 $P_{pq}^{s}$ 라고 하자. 그러면, 두 node 사이의 모든 가능한 루트를 거리 별로 정량화 한 값 (Communicability) 은 다음과 같다.

 

$C_{pq} = c_{s}P_{pq}^{s} + \sum_{l>s}^{\infty} c_{l}P_{pq}^{l} = c_{s}P_{pq}^{s} + \sum_{l>s}^{\infty} c_{l} \mathbf{A}_{pq}^{l}$

 

 여기서 $P_{pq}^{l} = \mathbf{A}_{pq}^{l}$ 인 이유는, 인접행렬을 곱하는 행위는 인접 node로의 이동을 의미하는데, 따라서 인접행렬을 l회 곱했을 때 pq 성분은 l회 이동했을 때 node p, node q 간에 닿을 수 있는 길의 개수가 되기 때문이다.

 

 계수 $c_{l}$는 subgraph 때와 마찬가지로, $\frac{1}{l!}$로 둔다. 그리고 편의상 가장 짧은 거리 s 이하에서는  도달하는 path가 없기 때문에 $P_{pq}^{l}$이므로, 이를 합쳐 쓰면, 다음과 같다.

 

$C_{pq} = \sum_{l=0}^{\infty} \frac{1}{l!} \mathbf{A}^{l}_{pq} = (e^{\mathbf{A}})_{pq}$

 

 subgraph와 형태는 같고, 성분만 다르다. 이를 인접행렬 A의 고유값 $\lambda$과 고유벡터 $\mathbf{\phi}$를 이용해서 나타내면, 

 

$C_{pq} = \sum_{j} \mathbf{\phi_{j}}(p) \mathbf{\phi_{j}}(q) e^{\lambda_{j}}$

 

 

---

Communicability betweenness centrality

 

 Communicability 를 betweenness 개념으로 확장시킬 수 있다. betweenness는 네트워크 상 두 지점을 연결하는 모든 shortest 경로 중 특정 node 또는 edge가 포함되는 횟수를 정량화 한 값으로, 특정 node 또는 edge가 얼마나 짧은 거리의 path를 매개하는지 나타낸다. 

 

 Communicability 또한 전달성의 관점에서 보면, 특정 node 'r'이 있고 없고에 따라 변화하는 전달성은 'r'이 지닌 betweenness를 정량화 한다.

 

 인접행렬 $\mathbf{A}$ 와 여기서 node r과 관련된 모든 link를 제거한 행렬 $\mathbf{A} + \mathbf{E}(r)$ 을 이용해 node r의 betweenness를 다음과 같이 나타낼 수 있다.

 

$ \omega_{r} = \frac{1}{C} \sum_{p} \sum_{q} \frac{ (e^{\mathbf{A}})_{pq} - (e^{\mathbf{A} + \mathbf{E} (r)})_{pq} }{ (e^{\mathbf{A}})_{pq} } $ 

$ p \neq q, p \neq r, q \neq r$

 

p와 q 사이에 r을 거치는 path가 거의 없을 경우, 우항은 0에 가까워지지만,

r을 거치지 않고서는 p와 q가 연결될 수 없는 경우에는 1에 가까워진다. 가장 극단적으로 r이 중심에 있는 star 모양의 network를 생각해볼 수 있는데, 이 때는 우항이 1이 되어

 

$\omega_{r} = \frac{(n-1)(n-2)}{C}$

 

가 된다. 고로, 계수 C를 $(n-1)(n-2)$ 로 두어 star graph와 같은 극단적인 케이스를 1로 두는 것이 일반적이다.

---