그래프 중심성(Katz, Engenvector, PageRank, etc..)

Contents

 

Centrality concepts

Centrality concepts는 그래프에서 어떤 노드가 얼마나 중요한지 측정하는 것이다. 중심성의 개념은 여러 가지 방법으로 측정할 수 있으며, 중심성을 측정하는 척도의 종류는 다음과 같다.

• 연결 중심성(Degree Centrality)
• 고유벡터 중심성(Eigenvector Centrality)
• 카츠 중심성(Katz Centrality)
• 페이지랭크(PageRank)
• 매개 중심성(Betweeness Centrality)
• 근접 중심성(Closeness Centrality)

 

연결 중심성, 고유벡터 중심성, 카츠 중심성, 페이지랭크 중심성과 같은 경우는 연결성을 바탕으로 중심성을 측정하는 방법이고, 매개 중심성, 근접 중심성과 같은 경우는 위상학적 관점으로 중심성을 측정하는 방법이다.

연결 중심성(Degree Centrality)

연결 중심성은 중심성을 측정하는 척도 중 가장 간단한 척도다. 하나의 노드에 연결된 엣지의 수를 중심성으로 평가한다. 소셜 네트워크를 예로 든다면, 한 사용자의 친구가 더 많을수록 해당 사용자의 중요도를 높에 보는 것이다. 만약 인스타그램처럼 팔로우, 팔로워가 있는 경우에는 조금 다르다. 팔로우와 팔로워는 하나의 방향성으로 보는 것이기 때문이다. 단순이 해당 수치만 가지고 평가한다면 규모에 따라 값이 편향을 가질 수 있기 때문에 정규화하는 방법도 사용한다. 

 

예시

\[ C_D(i) = \frac{k_i}{|V|-1} \]

고유벡터 중심성(Eigenvector Centrality)

인스타그램을 예로 들어보자. 사용자가 돈으로 허위 사용자를 매수해 팔로워의 수를 늘렸다면 이 사용자의 연결 중심성은 높게 나타난다. 그럼 이 사용자는 중요하다고 할 수 있을까? 이런 경우에 사용되는 것이 고유벡터 중심성이다. 고유벡터 중심성은 중요한 노드와 많이 연결된 노드가 중요하다는 가정에서 시작한다. 단순히 해당 노드의 숫자만을 고려하는 것이 아니라 다른 노드의 중심성까지 고려해 계산하는 방법이다. 

\[ x_i =  \sum_j A_{ij} x_j \rightarrow x_i = \frac{1}{\lambda} \sum_j A_{ij} x_j \rightarrow \lambda x = Ax \]

\[ Ax = \lambda x \]

위 수식을 보면 고유값과 고유벡터를 볼 수 있다. 이때 $x$는 고유벡터이자 중심성을 나타내는 행렬이고, $A$는 인접 행렬(adjacent matrix)을 의미한다. $\lambda$는 고윳값을 의미한다. 제일 처음 다루었던 행렬에 대해서 고윳값을 구하면 다음과 같다.(python의 힘을 빌려..)

a = np.array(
    [[0, 1, 1, 0, 0],
    [1, 0, 1, 1, 1], 
    [1, 1, 0, 1, 0],
    [0, 1, 1, 0, 0], 
    [0, 1, 0, 0, 0]]
)
eigen_value, eigen_vector = np.linalg.eig(a)
np.round(eigen_value, 4)
# array([ 2.6855, -1.7491, -1.2713, -0.    ,  0.3349])

\[ \begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ \end{bmatrix} \ \cdot \ \begin{bmatrix} 0.4119 & 0.4581 & -0.2834 & 0.7071 & -0.2004 \\ 0.5825 & -0.6478 & -0.4008 & 0. & 0.2835 \\ 0.5237 & -0.1534 & 0.7611 & -0. & -0.3506 \\ 0.4119 & 0.4581 & -0.2834 & -0.7071 & -0.2004 \\ 0.2169 & 0.3704 & 0.3153 & 0. & 0.8464 \\ \end{bmatrix} \] 

\[= \begin{bmatrix} 2.6855 \\ -1.7491 \\ -1.2713 \\ -0. \\ 0.3349 \end{bmatrix} \ \cdot \ \begin{bmatrix} 0.4119 & 0.4581 & -0.2834 & 0.7071 & -0.2004 \\ 0.5825 & -0.6478 & -0.4008 & 0. & 0.2835 \\ 0.5237 & -0.1534 & 0.7611 & -0. & -0.3506 \\ 0.4119 & 0.4581 & -0.2834 & -0.7071 & -0.2004 \\ 0.2169 & 0.3704 & 0.3153 & 0. & 0.8464 \\ \end{bmatrix} \]

$ \lambda = \begin{bmatrix} 2.6855 & -1.7491 & -1.2713 & -0. & 0.3349 \end{bmatrix}$가 고윳값을 의미한다. 가장 큰 고윳값과 대응되는 고유 벡터를 추출하면 $ \begin{bmatrix} 0.4581 & 0.5825 & 0.5237 & 0.4119 & 0.2169 \end{bmatrix} $가 된다. 2번째 노드가 가장 많은 Degree를 나타내고 있어 연결 중심성도 가장 높지만 고유벡터 중심성도 가장 높은 값을 나타내고 있다. 원래는 열벡터가 맞지만 화면의 구성상 행벡터로 표현하였다. 

 

 

카츠 중심성(Katz Centrality)

카츠 중심성은 고유벡터 중심성의 문제점을 보완한 지표다. 특수한 경우 위의 예시처럼 중심성이 0이 나올 수 있다. 이러한 문제를 방지하기 위해 모든 노드 중심성에 상수값을 더하는 방식이 카츠 중심성이다. 

\[ \text{C} = \alpha \text{AC} + \beta \text{I} \]

일반적으로 $\alpha < \frac{1}{\lambda}$로 가장 큰 고윳값으로 설정하고, $\beta$는 임의의 값으로 설정한다. $\alpha=1, \beta=0$인 경우 고유벡터 중심성과 동일한 결과가 나온다.

 

페이지랭크(PageRank)

페이지랭크는 카츠 중심성을 개선한 알고리즘이다. 카츠 중심성의 경우 한 노드의 중요성이 연결된 다른 노드로 전부 전파되는 특징이 있다. 하나의 노드가 중요하다고 계산되는 경우 그 노드와 연결된 다른 노드들도 전부 중요도가 높아지는 문제가 발생한다. 각 노드의 영향력을 다른 노드에 전파하는 경우 연결된 엣지의 수로 나누어 영향력을 감소시켰다. 

\[ \text{C} = \alpha \text{A}\text{D}^{-1} \text{C} + \beta \text{I} \]

동일한 수식처럼 보이지만 $\text{A}$와 $\text{C}$사이에 대각행렬(diagonal matrix) $\text{D}$로 대각 성분을 각각의 노드에 연결된 엣지의 수를 넣는 것이다. 예시는 다음과 같다. 

\[ \begin{bmatrix} 2 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \]

 

매개 중심성(Betweenness Centrality)

매개 중심성은 다른 노드들이 해당 노드를 통과하는 경로의 수에 따라 결정된다. 고속도로를 예로 들어보자. 우리는 서울에서 용인이나 수원 등 경기도로 내려갈 때 경부고속도로를 타고 내려간다. 이때 만약 경부고속도로에 사고가 나서 도로를 통제할 경우 얼마나 많은 사람들이 피해를 입을까 생각해보면 매개 중심성에 대해서 쉽게 이해할 수 있을 것이다. 또한, 추천 시스템에서 사람들의 여행 경로를 살필 때 사람들이 이 구간을 지나갈 때 들리는 여행지를 파악하면 해당 여행지의 중요도를 알 수도 있을 것이다. 

 

$V_1$에 대한 매개 중심성을 알아보자. $V_1$에 대한 매개 중심성을 구하기 위해서는 다른 노드들의 이동 경로를 알고 있어야 한다. $V_2-V_3$, $V_2-V_4$, $V_2-V_5$, $V_3-V_4$, $V_3-V_5$, $V_4-V_5$를 살펴보면 그 어느 경로도 $V_1$을 통과하지 않는다. 따라서, $V_1$의 매개 중심성은 0이 된다. 마찬가지로 다른 노드에 대해서도 해보자. 

$V_2$를 계산할 때 다른 노드들의 이동 경로는 $V_1-V_3$, $V_1-V_4$, $V_1-V_5$, $V_3-V_4$, $V_3-V_5$, $V_4-V_5$가 된다. 이 때 $V_1-V_4$일 때, $V_1-V_2-V_4$ 또는 $V_1-V_3-V_4$을 통해 가는 경우가 있다. 이 경우에는 1/2=0.5로 계산한다. 나머지를 계산하면 $V_1-V_5$=1, $V_3-V_5$=1, $V_4-V_5$=1로 V_2의 매개 중심성은 3.5가 된다. 이와 같은 방식으로 진행하다보면 다음과 같은 매개 중심성 벡터를 구할 수 있다. 

\[ \text{C} = \begin{bmatrix} 0 & 3.5 & 1 & 0 & 0 \end{bmatrix} \]

이렇게 매개 중심성을 구하게 된다면 그래프의 규모가 커질수록 값이 달라질 수 있다. 따라서 정규화가 요구되는데, 정규화 수식은 다음과 같다. 

\[ \text{Max Betweeness Centrality} = \frac{(\text{N}-1) \times (\text{N}-2)}{2} = \sum_{s < t} \frac{n^i_{st}}{g_{st}} \]

undirected graph인 경우에는 $s<t$로 구하면 되지만, directed graph인 경우에는 양쪽 방향을 모두 확인해야하기 때문에 $s, t$ pair를 모두 구하여야 한다. 이 때, directed graph면 중복을 제거할 필요가 없기 때문에 $\frac{(N-1) \times (N-2)}{1}$로 바뀐다. 

근접 중심성(Closeness Centrality)

근접 중심성은 중요한 노드일수록 다른 노드까지 도달하는 경로가 짧을 것이라는 가정을 두고 있다. 근접 중심성은 타깃 노드에서 타깃 노드를 제외한 다른 노드까지 도달하는 최소 경로의 평균을 구한 다음 역수를 취하면 끝이다. 근접 중심성을 계산하는 수식은 다음과 같다. 

\[ \text{Closeness Centrality}(\text{A}) = \frac{1}{\frac{1}{N-1} \times \underset{X \neq A}{\sum} \text{l}_{\text{X,A}}}  = \frac{N-1}{\underset{X \neq A}{\sum}\text{l}_{\text{X,A}}} \]

 

이때는 specific context한 정보를 고려하여야 한다. 즉, 모든 모든 노드가 Connect 된 경우에 사용하여야 한다. 떨어져 있는 노드의 경우 무한대가 되기 때문이다.

\[ C_i = \frac{n-1}{\sum^n_{j=1} d_{ij}} \]

기본적으로 isolated node는 제거하는 형태로 진행하여야 될 것이다. 어떤 도메인에서 적용해야 되는 지 먼저 생각하여야 한다.