Node Centrality metrics

노드 중심성

---

우리는 이 그래프에서 어떤 노드가 중심인지 혹은 어떤 노드가 중요한지 알 수 있을까?
아마도 원의 크기를 통해 유추할 수 있을 것이다.
하지만 만약 아래와 같은 그래프가 들어온다고 생각하여보자

어떤 노드가 다른 노드들보다 중요한지 한번에 알 수 없을 것이다.
즉 우리는 이와 같은 그래프들에서 중요한 노드를 찾아내어 맨 위에 있는 그래프와 같은 그래프를 만들 수 있어야 한다.

그렇다면 무엇이 중요한 노드 혹은 중심 노드일까?
우리는 이 중요하다의 기준을 정해놓아야한다.
이와 같이 미리 중요하다라는 기준을 정해놓은 것은 노드 중심성 지표라고 하고 대표적인 몇가지 예시를 살펴보자

Degree Centrality

연결 중심성이라고 불리는 것이다.
이는 말 그대로 degree 즉 현재 노드의 이웃의 수를 기준으로 중심 노드를 찾는 것이다.
"degree가 높다 == 중요하다" 라는 개념으로 degree가 가장 높은 노드가 가장 중요한 노드가 된다.

$C_D(i) = k(i) = \sum_jA_{ij}$

인접행렬을 이용하여 i번째 노드의 연결중심성을 구하는 공식이다.

이 간단한 공식에서 조금 생각해보면 만약 10001개의 노드가 있고 1개의 중심 노드에 10000개의 노드가 연결되어 있거나 5개의 노드가 있고 1개의 중심노드에 4개의 노드가 연결된 상황을 생각해보자.
아래와 같은 모습을 생각해보자

그렇다면 전자의 경우 중심 노드의 연결중심성 값은 10000일 것이고 후자는 4일 것이다.
하지만 우리는 이 두 그래프의 생김새가 동일하고 중심성의 정도도 동일할 것이라 생각할 수 있다.

즉, 그래프의 스케일에 따라서 지표가의 차이가 크게 나므로 다른 그래프와의 비교를 위해서라도 이를 정규화 시킬 필요가 있다.

$C^*_D(i) = \frac{k(i)}{N-1}$

정규화 시킨 공식은 다음과 같고 현재 노드를 제외한 N-1개의 노드로 나누어 주는 것을 알 수 있다.
이를 통해 중심성이 높은 노드의 경우 중심성 값이 1에 가까울 것이고 낮은 경우 0에 가까워질 것이다.

하지만 이 중심성의 경우 각 노드의 너무 지역적인 부분만 바라보고 전체적인 부분은 보지못한다는 큰 단점이 존재한다.

위와 같은 그림을 생각해보자.
이정도 그래프는 우리가 쉽게 파란색이 중심이라 생각하겠지만 연결중심성은 빨간색이 중심이라고 말한다.
따라서 굉장히 단순하나 이러한 국지적인 관점만 본다는 문제를 지니고있다.

Closeness Centrality

다음은 근접 중심성이다.
위 근접 중심성은 한 개의 노드에서 다른 모든 노드에 도달할때 걸리는 최단 거리의 합이다.
이는 한 노드에서 다른 모든 노드까지의 거리를 고려한다는 점에서 아까 위에서 본 국지적인 관점을 해결할 수 있는 방식이다.

$C_C{i} = \frac{1}{\sum_jd(i,j)}$

모든 최단거리의 합의 역수이고, 역수인 이유는 중심성이 클수록 중심이라는 일관성을 위해 거리의 합이 적을수록 중심성이 높도록 하기위함이다.

위의 예시를 살펴보면 노드와 노드간의 모든 최단거리를 구하고 이에 대한 합이 가장 적은 노드를 순서대로 중심성이 높다라고 판단할 수 있다.

이 또한 정규화가 가능한데

$C_C^*{i} = \frac{N-1}{\sum_jd(i,j)}$

다음과 같다.

하지만 이 중심성 지표는 연결요소가 여러 개라 노드간의 거리가 존재하지 않는 노드가 존재할 경우 사용할 수 없다. 두 노드 상의 거리가 발산하기 때문이다.

Betweenness Centrality

이는 매개 중심성이라 불린다
먼저 공식을 살펴보면

$C_B(i) = \sum_{s\ne t \ne i}\frac{\sigma_{st}(i)}{\sigma_{st}}$

위와 같고 여기서 i의 중심성을 구하기 위해서 s,t를 사용한다.
공식을 자세히 살펴보면 $\sigma_{st}$는 s와 t의 최단 경로의 개수로 해석할 수 있고 $\sigma_{st}(i)$는 s와 t의 최단 경로 중 i를 지나는 것의 개수라고 볼 수 있다.

즉 i의 매개 중심성을 구하기 위해 나머지 모든 정점의 조합으로부터 최단거리의 개수를 구하고 그 중 i를 지나는 최단거리의 개수의 비율의 합이 된다.

이 또한 정규화 시킬 수 있는데

$C_B^*(i) = \frac{2}{(N-1)(N-2)}\sum_{s\ne t \ne i}\frac{\sigma_{st}(i)}{\sigma_{st}}$

여기서는 합하는 개수가 $N-1$이 아니라 자신을 제외한 정점의 조합들이기 때문에 총 $\frac{(N-1)(N-2)}{2}$가 되고 이를 나눠주어 정규화 시킬 수 있다.

4의 매개 중심성을 구한다고 했을때 다음과 같고 이때 0.5 + 0.5로 매개 중심성은 1이 되게 된다.

Eigenvector Centrality

고유벡터 중심성
선형대수학에 나오는 고유벡터를 사용하고 중심성을 구하는 방식이다.

이 중심성의 배경을 생각하자면 위에서 본 중심성은 단순히 개수라는 수치를 고려하였다.
하지만 쉽게 생각해보면 SNS에서 팔로워가 많은 사람들은 보통 인플루언서라고 칭한다.
하지만 요즘 SNS 팔로워를 늘리기위해 의미없는 계정을 사서 인위적으로 팔로워를 늘리는 사람들을 볼 수 있다.
하지만 과연 이런 사람들이 높은 중심성은 가진 사람이라고 할 수 있을까?

이러한 문제를 해결하기위해 단순히 연결 개수가 아닌 연결된 노드의 중심성까지 고려해야한다.
즉 고유벡터 중심성에서는 각 연결된 노드에 가중치를 부여하여 계산할 수 있다.

이전에는 각 노드의 가중치가 모두 동일하다라고 생각할 수 있다.
하지만 여기서는 각 노드의 가중치가 다를 수 있다는 전제를 가질 수 있다.

$v_i = \sum_j{A_{ij}v_j}$

이는 현재 노드의 중심성을 구할 때 인접노드의 가중치의 합을 사용한다.
하지만 공식에서 볼 수 있다시피 이 방식은 재귀적인 절차를 요구한다.

하지만 현재 공식에서 재귀적으로 계속 진행할 경우 값은 지속적으로 발산한다는 것을 알 수 있을 것이다.

예를 들어 1,2,3번 노드가 삼각형의 형태로 서로 연결되어있다고 생각하자. 그리고 초기의 가중치는 모두 1이다.

위에가 초기이고 아래가 한번의 사이클을 진행한 상태이다.
이와 같은 과정이 재귀적으로 반복되면 값은 끝없이 발산하게 될 것이다.

이때 우리는 적당한 $\lambda$를 사용한다.

$v_i = \frac{1}{\lambda}\sum_j{A_{ij}v_j}$

이 수렴하는 적당한 $\lambda$가 있다라고 말하고 이 $\lambda$를 고윳값이라고 부른다.
이 식을 조금 일반화 시키면

$Av = \lambda v$ 가 되고 이는 우리가 일반적으로 알고있는 고윳값을 구하는 공식이 된다.

이곳에서 우리는 가중치에 해당하는 $v$ 즉 고유벡터를 구하면 된다.
이는 선형대수학에서 배운 고윳값 구하는 공식을 사용하면 되고 이때 eigenvalue가 가장 클 때의 eigenvector를 중심성으로 사용한다.
eigenvalue가 가장 크다라는 것은 일반적으로 변환의 영향력이 가장 크고 혹은 중요한 노드의 중요성이 더 강조될 때를 의미한다.

정리

추가적으로 위와 같은 특징들 때문에 Closeness Centrality를 통해 중심성이 높다고 판단되는 노드는 일반적으로 클러스터의 중심이 된다.
Betweenness Centrality는 클러스터의 연결부분에 위치하게되고 Eigenvector Centrality는 일반적으로 서로 밀집된 형태를 지니게 된다.

A : Degree
B : Closeness
C : Betweenness
D : Eigenvector