[네트워크 이론] 전달 가능성(Communicability) & 부분 그래프 중심성(Subgraph Centrality)

네트워크 이론에서는 전달가능성(Communicability)이라는 개념을 다룹니다. 두 노드가 얼마나 잘 연결되어 있는지를 보는 개념이라고 할 수 있는데요, 이 포스트에서는 전달가능성의 개념과 계산방법 및 그와 관련된 여러 이야기에 대해서 다뤄보겠습니다.

전달 가능성(Communicability)

학교에서 소문이 퍼지는 일을 생각해봅시다. 소문은 사람에서 사람에게로 1대1로만 퍼진다고 가정하고, 둘이 친한 사이일수록 더 잘 퍼진다고 합시다. 만약 사람 A가 어떤 정보를 알고 있다고 할때, 이 정보가 다른 사람 B에게 얼마나 잘 퍼지는지 어떻게 계산할 수 있을까요? 만약 A와 B가 직접 친한 사이라면 A가 직접 B에게 그 정보를 전달해줄테니 금방 퍼질거라고 생각할 수 있습니다. 혹은 둘 사이가 전혀 모르는 사이라도, A가 C와 친하고, C가 B와 친할 경우에 A->C->B의 순서로 정보가 퍼질 수도 있겠죠. 학교가 크고 사람이 많다면 여러 관계가 형성될테니 A에게서 B에게로 정보가 퍼지는 일은 여러 단계를 거칠 수도 있습니다. 그렇기에 정보가 퍼지는 정도를 보려면 단순히 A-B가 연결되었는지 여부만 보는 것으로는 부족합니다. 여러 단계를 거치는 일을 고려하기 위해서 전달 가능성의 개념이 고안된것이죠.

네트워크의 노드 간 연결은 행렬로 나타낼수 있다는 것은 이전 글에서도 여러 번 설명했으니 중언부언하지 않겠습니다. 즉, 네트워크의 연결상태를 나타내는 인접 행렬이 A라고 하면 다음 식은 i->j 연결의 강도를 나타냅니다.

: i->j로 이어지는 연결 강도

연결 관계를 행렬로 나타내면 좋은 점은 복잡한 연산을 간단한 행렬 연산으로 바꿔서 쓸 수 있다는 것이죠. 위에서 등장한 A를 제곱할 경우 그 행렬은 2단계에 거쳐서 i->j로 연결되는 강도를 나타내는 행렬이 됩니다. 더 일반적으로 말해서 A^n의 경우 n단계를 거쳐 i->j로 연결되는 강도를 나타내는 행렬이 됩니다.

: i->j로 n단계를 거쳐 이어지는 연결 강도

노드 i에서 j로 이어지는 전달가능성을 보기 위해서는 단순히 i, j가 바로 연결되는 경우 말고, 2단계를 거쳐 연결되는 경우, 3단계, ... n단계를 거쳐 연결되는 경우를 모두 살펴봐야합니다. 하지만 직접 연결되는 경우처럼 연결이 강한 경우는 없겠죠? 따라서 2단계, 3단계 ... n단계로 점차 연결되는 단계가 늘어날수록 가중치를 낮게 주어서 고려하는게 맞겠습니다. 따라서 다음과 같은 식을 생각해 볼수 있겠죠.

2단계의 경우 그 값을 2!로 나누어주고, 3단계의 경우 3!로, ... n단계의 경우 n!로 나누어주어서 합쳐보았습니다. 무한 합이기 때문에 이를 계산하려면 연산비용이 큰 행렬의 거듭제곱을 수없이 반복해야합니다. 큰 네트워크에 대해 수행하기에는 쉽지 않아보입니다. 그런데 왜 가중치를 1/n이 아니라 굳이 1/n!로 주었을까요? 사실 여기에는 여러 이유가 있습니다.

1. n!로 나눠주면 모든 A에 대해서 항상 수렴한다.

2. 그리고 이 식은 수학적으로 아주 의미가 있는 식이다.

3. 2번의 수학적 의미 덕분에 위 계산을 빠르게 할 수 있다.

2, 3번을 좀더 설명하기 위해 C_ij를 성분으로 가지는 행렬 C를 다음과 같이 정의해보겠습니다.

미적분을 공부해보신 분들은 많이 접한 식일 겁니다. 위 식은 사실 지수 함수 e^x,  exp(x)의 테일러 전개식과 일치합니다.

기본적으로 지수 함수는 물론 실수(와 복소수)에 대해서 정의되지만, 수학자들은 전개식의 유사성을 통해 행렬에 대해서도 지수 함수를 정의했습니다. 따라서 위 식의 C는 다음과 같이 쓸 수도 있죠.

수학자들은 행렬의 지수 함수에 대해서도 연구했는데, 위와 같이 정의된 지수의 행렬 거듭제곱 연산도 일반 거듭제곱과 마찬가지로 다음의 성질이 잘 성립합니다.

따라서 우리는 C_ij를 구하기 위해 그냥 단순히 A를 수없이 거듭제곱하고 합하는 것보다 좀 더 빠른 방법을 사용할 수도 있겠죠. 그냥 거듭제곱할 경우 합하는 항 이 충분히 작아지기 위해서는 n이 충분히 커져야합니다. 하지만 A 대신 B = A/2의 지수 함수를 계산할 경우 행렬의 성분이 1/2이 된 덕분에 수렴이 훨씬 빨라지겠죠. 이렇게 e^B를 계산한 뒤 (e^B)^2을 하면 e^A를 얻을 수 있습니다. 이것을 반복적으로 적용하면 C를 계산하는 속도를 매우 빠르게 할 수 있습니다.

전달 가능성을 정의할때는 단순히 e^A가 아니라 전달하는 정도를 결정하는 계수 β(inverse temperature 또는 discount parameter라고 부릅니다)를 덧붙여

와 같이 정의합니다. β가 0에 가까울수록 모든 노드끼리의 전달 가능성은 0에 가까워지고, 커질수록 전달 가능성은 커지겠죠?

전달 가능성 계산 예제

앞에서 늘 쓰던 예제입니다. 위 네트워크의 인접 행렬 A는 다음과 같습니다.

전달 가능성을 계산하기 위해 C = e^A를 계산하면 다음과 같습니다. (편의상 β = 1로 두었습니다.)

의미없는 대각선 값들을 빼고 나머지 부분을 봅시다. A-D의 전달가능성은 1.08이고, A-C의 전달가능성은 2.10입니다. A-D, A-C 모두 직접 연결되지는 않고, 2단계를 거쳐 연결되었지만 A-C의 경우 연결방법이 더 다양하기 때문에 높은 전달가능성 값이 나왔습니다. 전달 가능성 값이 제일 큰 경우는 B-E로 4.27의 값이 나왔네요.

근데 대각선의 값들은 무엇을 의미할까요?

부분그래프 중심성(Subgraph Centrality)

Estrada는 부분그래프 중심성이라는 개념을 제안했는데요, 부분그래프 중심성은 쉽게 말해서 한 노드가 얼마나 많은 닫힌 경로를 가지는지를 바탕으로 그 노드의 중심성을 판단하는 방법입니다. 2번만에 자기자신으로 돌아오는 경로의 수, 3번만에 자기 자신으로 돌아오는 경로의 수, ... n번만에 자기 자신으로 돌아오는 경로의 수를 모두 합하여 그 노드의 중심성을 파악하는 것인데, 위에서 했던 것처럼 n길이의 경로에는 1/n!의 가중치를 부여합니다. 그 결과 위에서 전달 가능성을 계산하는데 사용한 식과 동일한 식이 나타나게 됩니다.

즉 위에서 얻은 대각선의 값들이 각 노드의 부분그래프 중심성(SC)이 되는거죠.

자명하게도 노드 E가 5.21로 가장 큰 중심성 값을 가지네요. 하지만 이 값은 네트워크 규모에 따라 중심성 크기가 오락가락하기 때문에, 이 값을 정규화하여 일정한 범위 안으로 넣어주면 좋겠죠? 그래서 모든 노드들의 부분그래프 중심성 값의 합을 구해 그것으로 나눠주어 정규화를 진행합니다. 이때 모든 중심성 값의 합을 Estrada index라고 하는데, 이 값은 다음과 같다고 Estrada가 증명했습니다.

즉, 인접행렬의 고윳값의 exp의 값들의 합과 같습니다. 여기서는 이미 위에서 각 노드들의 SC값을 구했으므로 그 값들을 합해서 EE를 계산해보겠습니다.

EE = 3.10 + 4.36 + 3.10 + 1.74 + 5.21 = 17.51

따라서 정규화된 부분그래프 중심성 값은 다음과 같습니다.

행렬 가지고 놀기

위에서 제시된 행렬을 가지고 좀더 쪼물딱거리면 더 재밌는 것들도 해볼 수 있습니다. 다음과 같이 길이가 짝수인 경로와 홀수인 경로를 나눠서 계산해볼 수도 있겠죠.

그리고 이 때 Even(A) = cosh(A)가 되고, Odd(A) = sinh(A)가 됩니다. 당연히 cosh(A) + sinh(A) = exp(A)가 되구요. 마찬가지로 쌍곡선 함수의 특징들을 이용해서 위의 값들은 효율적으로 계산될 수 있습니다. 근데 이게 무슨 쓸모가 있을까요?

이분 그래프(bipartite graph)라는 개념이 있습니다. 그래프의 모든 노드가 2가지 종류로 나뉘는 건데요, 같은 종류끼리는 절대 연결되지 않고, 다른 종류의 노드하고만 연결된 그래프를 가리킵니다. (위키백과 링크) 이 그래프의 특징은 모든 노드에서 자기 자신으로 돌아오는 닫힌 경로는 항상 짝수 길이라는 특징이 있습니다. 즉 홀수 길이의 경로의 수는 0인 것이죠. 따라서 이분 그래프에서는 Odd(A) = 0이 됩니다. 이를 이용해서 특정 네트워크가 얼마나 이분 그래프다운지를 판단하는 수치를 만들수도 있겠죠.

즉 cosh A의 대각합과 e^A의 대각합의 비율을 계산하여 그 값이 1에 가까울수록 이분 그래프에 가깝다고 볼 수 있겠죠.

카츠 중심성(Katz Centrality)

만약에 길이가 n인 경로에 대해서 1/n!로 가중치를 주는 것을 없애면 어떻게 될까요? 놀랍게도 그 결과는 앞에서 다루었던 Katz 중심성 값으로 수렴합니다. (알고보니 다 거기서 거기였던 중심성 척도들...)

이 경우 α이 중요합니다. α값에 따라서 무한 합의 수렴여부가 정해지니깐요. 일반적으로 다음과 같은 조건을 만족하면 행렬 A의 거듭제곱이 0에 수렴합니다. 

이 때 λ는 행렬 A의 고윳값 중 가장 큰 값입니다. 따라서 행렬 αA의 거듭제곱이 수렴하기 위해서는

의 조건을 만족해야합니다. (카츠 중심성에서 α의 요구조건이 여기서 나온것이라는것!) 이 조건을 만족할때 무한합 C는 수렴하게 되고 이때 이 무한합은 다음과 같이 표현가능합니다.

(무한등비급수의 합을 구하는 공식을 생각해보면 쉽게 이해할 수 있습니다.) 

위 식을 정리해보면

가 됩니다.

카츠 중심성의 정의 중 하나인 와 β=1 인 지점에서 일치하는것을 볼 수 있죠.

이 관점에서 볼때 카츠 중심성의 의미는 어떤 노드가 가지는 길이가 n인 닫힌 경로의 수를 α^n의 가중치를 두어 총합한 것이라고 볼 수 있습니다. 부분그래프 중심성은 여기에다가 가중치로 1/n!를 더 곱해준 것이구요.

링크

포스트의 많은 부분은 다음을 참고하였습니다. 

http://www.dsi.unive.it/isscn/wp-content/uploads/2014/07/Benzi1.pdf

https://en.wikipedia.org/wiki/Centrality

https://en.wikipedia.org/wiki/Matrix_exponential