[네트워크 이론] 다양한 중심성(Centrality) 척도들

세상의 많은 관계들을 수학적으로 나타내는데에는 그래프만큼 강력한 도구도 없습니다. 관계의 주체가 되는 행위자들은 Node로, 관계들은 Node사이를 연결하는 Edge로 나타낼 수 있기 때문이죠. 이렇게 주변에서 찾아볼 수 있는 관계를 수학적인 형태의 Graph로 바꾸면 여러 가지가 가능해지는데, 그 중 대표적인것이 중심성(Centrality) 계산입니다. 중심성은 그래프 상에서 어떤 Node가 가장 중요한지를 살피는 척도인데요, 여태까지 막연하게 여러가지 계산법이 있을거라고 생각은 했지만, 실제로 공부는 해보지 않았었네요. 그래서 이번에 Social Media Mining을 공부하면서 관련 이론을 정리해보려고 합니다. 

(다음 내용은 Zafarani, R., Abbash, M.A., & Liu, H, 2014, Social Media Mining : An introduction 의 3.1장 내용을 바탕으로 정리하였습니다.)

먼저 다음과 같은 네트워크를 예시로 들도록 하겠습니다. 편의를 위해 무방향성, 가중치 없는 그래프를 만들어봤습니다.

사실 누가봐도 노드 E가 제일 중요해보이지만, 이를 수학적으로 계산하는 방법에는 어떤게 있는지 살펴봅시다. 먼저 위의 그래프는 5개의 노드로 이루어져 있으므로, 5x5 인접행렬 A로 나타낼 수 있겠죠.

A_ij는 노드 i가 j와 연결되어있는지를 나타냅니다. 위에서 예를 든것처럼 방향성이 없는 그래프의 경우에는 A_ij가 A_ji와 같습니다. 또한 간선 가중치가 없으므로 행렬의 각 성분이 가질 수 있는 값은 0(연결 안됨) 또는 1(연결 됨)이 되겠죠.

연결 중심성(Degree Centrality, Cd)

Cd는 가장 간단한 중심성 척도입니다. 한 Node에 연결된 모든 Egde의 갯수(Weighted 그래프일 경우에는 모든 Weight의 합)로 중심성을 평가합니다. 방향성이 있는 그래프일 경우에는 Node로 들어오는 Edge와 나가는 Edge가 다를 수 있죠. In-degree만 계산할 경우 그 노드의 인기도를 볼 수 있고, Out-degree만 계산할 경우 그 노드의 영향력을 살필수 있다고 흔히 얘기합니다.

하지만 단순 Cd로는 다른 네트워크끼리 중심성 비교를 수행하기 어렵습니다. 규모가 큰 네트워크일수록 당연히 Cd값도 커지기 때문에 공정한 비교가 안되죠. 따라서 정규화를 하여 사용하기도 합니다. 정규화 방법에는 네트워크 내 가능한 최대 Cd값인 N-1(N은 모든 노드의 숫자입니다.)으로 나눌 수도 있고, 혹은 실제로 해당 네트워크 내에서 나오는 가장 큰 Cd값으로 나누는 방법도 있습니다. 혹은 네트워크 내의 모든 Cd값의 합으로 나눠서 정규화하기도 합니다.

위의 예시에 적용해보면 E에 연결된 간선이 4개로 가장 많으므로 E가 가장 중심성이 높다고 볼수 있습니다. 모든 노드의 Cd값을 편의상 하나의 벡터로 나타낼 수도 있는데 그러면 위의 예시에서의 Cd값은 다음과 같이 표현할 수 있겠죠.

그리고 이 Cd를 계산하는 식은 굳이 수식으로 쓰겠다면 다음과 같습니다.

(여기서 1은 모든 성분의 값이 1인 1xN차 행렬입니다.)

고유벡터 중심성(Eigenvector Centrality, Ce)

하지만 무조건 연결된 노드가 많다고 중요한 노드가 되는 것은 아닙니다. 사실 중요한 노드와 많이 연결된 노드가 더 중요하겠죠. (페북 친구가 아무리 많다고 해서 유명인사인건 아니죠. 유명인사인 친구가 많을수록 유명인사라고 할 수 있을겁니다.) Cd는 단순히 연결된 노드의 숫자만 살핀다는 점에서 약점이 있습니다. 그래서 Ce에서는 중심성을 계산할때 다른 노드의 중심성을 반영해서 계산하는 방법입니다.

근데 이걸 계산하려고 보니 이상합니다. V_1의 중심성을 계산하려고 하는데, V_2, V_3 ... 의 중심성을 필요로하니깐요. V_2의 중심성을 계산하려고 하는데 V_1, V_3...의 중심성이 필요하고... 이걸 어떻게 계산할까요. 방정식을 세우면 다음과 같이 될겁니다.

A가 네트워크의 NxN 인접행렬이고 Ce가 중심성 값을 나타내는 1xN 행렬이라고 하면 위와 같은 식을 도출할 수 있습니다. 선형대수론을 따르면 이때 Ce는 A의 고유벡터, λ는 고윳값이라고 한답니다. 이를 계산하는 방법은 수학자들에게 맡겨두고, 인접행렬을 가지고 적절한 λ값에 대한 고유벡터를 계산하면 이것이 중심성을 나타내는데 쓰일수 있다는 정도로 정리하면 될듯합니다.

A가 5x5 행렬이기 때문에 가능한 고윳값이 5개가 나오는데, 가장 큰 고윳값 2.686...에 대응하는 고유벡터를 구하면 다음과 같습니다. (복잡한 계산식은 생략하도록 하겠습니다.)

마찬가지로 E가 1.247로 제일 중요한 노드로 나오는걸 확인할 수 있죠.

Katz 중심성(Katz Centrality, Ck)

Ce의 한계 중 하나는 방향성 비순환 그래프와 같이 특별한 경우에는 중심성이 0이 나오는 경우가 있다는 겁니다. 이를 방지하기 위해 모든 노드 중심성에 특정한 상수값을 더하는 방식이 Katz에 의해 제안되었습니다. 고유벡터 중심성의 변형버전이라고 볼 수 있겠죠. 

 (1은 모든 성분이 1인 1xN차 행렬입니다.)

대게 α < 1/λ이 되도록 잡고 (λ는 A의 고유값 중 가장 큰 값),  β는 적절한 값으로 실험을 통해 잡습니다.

α = 0.3,  β = 0.2 로 잡고 계산하면 다음과 같은 Ck값을 얻을 수 있습니다.

페이지랭크(PageRank, Cp)

아마 Cp가 지금까지 등장한 중심성 알고리즘 가장 성공한 알고리즘이라고 볼 수 있을텐데요, 이는 사실 Katz 중심성의 개량 버전이라고 볼 수 있습니다. Katz 중심성 계산식에서는 한 노드의 중요성이 연결된 다른 노드로 전부 전파되는 특징이 있습니다. 다르게 말하자면 한 노드가 매우 중요하게 계산될 경우, 그와 연결된 노드들도 같이 덩달아 중요도가 높아져버리는 문제가 생길 수 있다는 것입니다. 그렇기에 페이지랭크에서는 각 노드의 영향력을 다른 노드로 전파할 때, 외부로 향하는 모든 간선의 수(역시나 Weighted 그래프일 경우에는 Weight의 합)로 나누어 Out-edge로 영향력이 지나치게 퍼지는 것을 막았습니다.

(D는 각 노드의 외부로 향하는 간선의 수를 성분으로 가지는 NxN 대각행렬입니다.)

* 외부로 향하는 간선이 없는 노드의 경우 D의 역행렬을 계산할때 0으로 나누는 일이 발생하게 됩니다. 사실 외부로 영향을 미치지 않는 노드는 다른 노드의 중심성 계산에 영향을 미치지 않기 때문에 그 값을 0이 되지 않도록 1로 설정하거나 실제 계산에서는 제외하는 등의 방법을 사용합니다.

마찬가지로 대게 α < 1/λ이 되도록 잡고 (λ는 A의 고유값 중 가장 큰 값. 무방향성 그래프에서는 1이됩니다.),  β는 대게 0.15(랜덤 서퍼 모델)로 잡습니다.

위의 그래프를 예시로 페이지 랭크 값을 계산해볼게요. 먼저 D행렬은 다음과 같이 될 겁니다.

Katz에서와 같이 α = 0.3,  β = 0.2 로 잡고 계산하면 위의 공식이 수렴할때까지 반복하면 다음과 같은 페이지랭크 값을 얻을 수 있습니다.

지금까지 살펴본 4개의 중심성 척도는 한 노드가 다른 노드와 얼마나 연결되어 있는가를 중요성의 기준으로 삼았는데요, 그렇지 않은 척도도 있습니다.

매개 중심성(Betweenness Centrality, Cb)

이 중심성 척도는 노드들 간의 최단 경로를 가지고 계산됩니다. A도시의 중요성을 보기 위해서는 A를 제외한 도시에 사는 사람들이 다른 도시로 이동할때 얼마나 A를 거쳐가는지를 살펴보면 된다는 아이디어를 바탕으로 하고 있습니다. 그래프 이론의 용어로 다시 써보자면, 노드 A의 중요성은 A가 아닌 X, Y노드에 대해 X-Y의 최단 경로에 A가 포함되어있는 비율로 볼 수 있다는 거죠. 이 경우 노드 X에서 Y로 지나가는 최단 경로들이 항상 A를 거쳐간다면 그 값은 1이 됩니다. 반대로 노드 X,Y에 대해서 X에서 Y로 지나가는 최단 경로들이 하나도 A를 거쳐가지 않으면 그 값은 0이 됩니다. 이 값들을 A를 제외한 모든 노드들에 계산하여 합치면 그 값이 바로 Cb입니다. 

Cb값도 네트워크 규모에 따라 그 크기가 달라질 수 있으니 다른 네트워크와 비교하기 위해서는 정규화를 해줄 필요가 있습니다. 간단한 정규화 방법으로는 가능한 최대의 Cb값으로 나눠버리는 것입니다. 전체 노드의 갯수가 N개라고 하면, 한 노드 A를 선택하고 남은 노드의 갯수는 N-1개입니다. N-1개 중에서 순서 상관없이 2개를 뽑는 경우는 총 (N-1) * (N-2) / 2가지입니다. 이 값들이 모두 1이 나오는 경우가 최대값일테니 노드 갯수가 N인 네트워크의 최대 Cb값은 (N-1) * (N-2) / 2가 됩니다. 이 값으로 나눠서 정규화시키면 정규화된 Cb값은 항상 0~1사이에 위치하게 됩니다.

위의 그래프를 가지고 예를 들어봅시다. 노드 A의 매개 중심성을 계산하기 위해서는 A를 제외한 B~E들 간의 이동경로를 살펴봐야 합니다. B-C, B-D, B-E, C-D, C-E, D-E 중 어떤 경우도 A를 거쳐가는 일이 없습니다. 그러므로 이 경우는 계산할 것도 없이 Cb(A) = 0입니다.

B를 살펴볼까요? A-C, A-D, A-E, C-D, C-E, D-E 중에서 A-C의 경우 A-B-C 또는 A-E-C를 거쳐가는 경우가 최단 경로가 됩니다. 따라서 A-C의 경우 B를 거쳐갈 확률이 0.5입니다. 나머지는 경우는 없으므로 Cb(B) = 0.5입니다.

반면 제일 중심에 있어보이는 E를 살펴봅시다.

A-B, A-C, A-D, B-C, B-D, C-D 중에서 A-C의 경우 A-B-C, A-E-C의 경로가 있으므로 이 경우 E를 거칠 확률이 0.5, A-D의 경우는 A-E-D밖에 없으므로 확률이 1, B-D의 경우 B-E-D 밖에 없으므로 이 경우도 1, C-D의 경우 역시 C-E-D 밖에 없으므로 1입니다. 따라서 Cb(E) = 0.5 + 1 + 1 + 1 = 3.5입니다.

모든 중심성 값을 구해 벡터 형태로 표현하면

근접 중심성(Closeness Centrality, Cc)

근접 중심성은 중요한 노드일수록 다른 노드까지 도달하는 경로가 짧을 것이라는 가정을 기저에 두고 있습니다. 도시에 비유하자면, A도시에 사는 사람이 전국 각지로 가는데 걸리는 시간 평균과 B도시에 사는 사람이 전국 각지로 가는데 걸리는 시간 평균을 비교해서 A가 더 짧다면 더 중심적인 도시일거라는 거죠.

이를 수학적으로 계산하기 위해서 한 노드 A에서 A를 제외한 다른 노드들까지의 최단 경로의 길이를 평균을 내고, 그 값을 역수로 취합니다. (길이가 짧을수록 Cc값이 커져야하므로) 수식으로 쓰면 다음과 같겠죠.

(l은 두 노드 사이의 최단 거리를 뜻합니다.)

위의 그래프를 가지고 실제로 계산을 해보자면 A는 거리가 B까지 1, C까지는 2, D까지도 2, E까지는 1입니다. 따라서 A의 다른 노드까지의 평균거리는 1.5이므로 Cc(A) = 0.667 가 됩니다.

다른 경우도 모두 계산해서 벡터형태로 나타내면

조화 중심성(Harmony Centrality, Ch)

근접 중심성과 유사하지만, 최단거리의 평균을 역수를 취하는 것이 아니라, 최단거리의 역수를 평균을 취하는 방법이 있습니다. 조화 수열(Harmonic Number)에서 이름을 따와서 이를 조화 중심성이라고 부릅니다. (http://infoscience.epfl.ch/record/200525/files/%5bEN%5dASNA09.pdf)

만약 두 노드 사이의 경로가 존재하지 않을경우 최단거리를 무한대로 보고 최단거리의 역수는 0으로 취급합니다.

위의 그래프를 가지고 실제로 계산을 해보자면 A는 거리의 역수는 B까지 1, C까지는 0.5, D까지도 0.5, E까지는 1입니다. 따라서 A의 다른 노드까지의 평균거리는 0.75이므로 Ch(A) = 0.75 가 됩니다.

다른 경우도 모두 계산해서 벡터형태로 나타내면 다음과 같습니다.

지금까지 네트워크 이론에서 사용하는 여러 가지 중심성 척도를 살펴봤는데요, 각자 바탕으로 하는 아이디어가 다르므로, 실제로 같은 그래프에 사용하더라도 척도에 따라 중심성 값을 얻게 됩니다. 따라서 적절한 경우에 맞게 잘 사용하는게 필요하겠습니다!