[네트워크 이론] 노드 간 유사도(Similarity) 척도

앞서 중심성, 결집계수에 대해서 다뤄보았으니, 이제 네트워크 이론에서 두 노드가 얼마나 유사한지를 계산하는 방법에 대해서 논해봅니다. 어떻게 두 노드가 유사한지를 판단할 수 있을까요? 가장 간단한 방법으로는 두 노드의 이웃이 얼마나 겹치는지를 살펴볼 수 있겠죠. 만약 모든 이웃이 겹친다면 두 노드는 아예 똑같은 노드, 겹치는 이웃이 하나도 없다면 전혀 다른 노드라고 봐도 되겠죠?

구조적 등위성(Structural Equivalence)

앞서 설명한 겹치는 이웃의 수를 보고 유사도를 판단하는 방법을 구조적 등위성이라고 합니다.  SNS를 예시로 설명하자면, 친구가 겹치는 사람이 많을 수록 유사한 유저라고 본다는 것이죠.

(N(i)는 노드 i의 이웃 노드들의 집합)

이때 i와 j의 단순 유사도는 i의 이웃 집합과 j의 이웃 집합의 교집합의 원소 갯수가 됩니다. 다만 이 수치는 그래프 크기에 따라 범위가 달라지므로 정규화할 필요가 있는데 여러 기법이 있습니다. 흔히 쓰이는 코사인 유사도나 자카드 유사도 뿐만 아니라 피어슨 상관계수 등 여러가지 척도가 이용 가능합니다.

(자카드 유사도. 0~1 범위)

(코사인 유사도. A_i를 인접행렬의 i행 벡터라고 보면 벡터 식으로도 표현가능합니다. 범위는 -1~1)

(유클리드 거리. 0일때 완전 일치하고, 커질수록 불일치함. 역수를 취해주면 유사도 척도로 사용가능합니다. 범위는 0~∞)

(피어슨 계수. a는 노드i의 이웃과의 평균 연결가중치, b는 노드j의 이웃과의 평균 연결가중치. I는 모든 성분이 1인 n차 벡터. 범위는 -1~1)

역시나 수식으로만 보면 이해가 잘 안되니깐 실제 그래프를 가지고 유사도를 산출해봅시다.

B와 D가 얼마나 유사한지를 계산해볼게요. 일단 B와 D의 이웃을 살펴보죠.

N(B) = {A, C, E}

N(D) = {E}

벡터 형태로 쓰자면

A_B = (1, 0, 1, 0, 1)

A_D = (0, 0, 0, 0, 1)

이 됩니다.

먼저 단순 유사도는 겹치는 이웃이 1개이므로 1이 됩니다.

자카드 유사도는 B,D의 겹치는 이웃 1개를 전체 이웃 3개로 나누면 되므로, 0.333

코사인 유사도는 두 벡터의 내적 값인 1에서 두 벡터의 크기 √3, 1을 나눠주면 되므로, 

유클리드 거리는 (1, 0, 1, 0, 1) - (0, 0, 0, 0, 1)의 크기를 구하면 되므로

피어슨 계수의 경우 조금 계산이 복잡한데, 일단 B의 이웃과의 평균 연결가중치를 구하면, 전체 5개의 노드중 3개가 연결되어 있으므로 3/5 = 0.6, 마찬가지로 D의 평균 연결가중치는 1/5 = 0.2가 됩니다. 이제 피어슨 계수를 계산해보면

(친절하게 풀어썼는데, 너무 지저분해 보여서 괜히 쓴거같기도 하고...)

같은 차원의 두 벡터에 대해 사용할 수 있는 모든 유사도 계산법은 다 사용할 수 있습니다. 어떤 녀석이 어떤 특징을 가지는지는 여기서 다 설명할 필요는 없을거 같으므로 생략하겠습니다.

동형적 동위성(Automorphic Equivalence)

위에서 살펴본 구조적 동위성은 두 노드가 공유하는 이웃을 가질때만 유사한 노드로 보는 방법입니다. 하지만 같은 이웃을 공유하지 않아도 그 형태가 유사할 수도 있습니다. 이 형태를 살피는 방법이 동형적 등위성입니다. 가족 그래프를 예로 들자면, 어머니에게 자식 2명이 있고, 이모에게 또 다른 자식 2명이 있다면, 이 6명의 가족 구성원들은 하나의 네트워크를 이루게 되지요. 이때 엄마와 이모는 같은 이웃을 전혀 공유하지 않지만 2명의 자식을 두고 있다는 사실을 공유하며 대칭을 이룹니다. 이때 이모와 엄마는 동형적 등위성을 가진다고 말합니다. 만약 이모의 자식이 1명일 경우는 이모와 엄마는 대칭을 이루지 않기 때문에 등위성을 가지지 않는다고 볼 수 있구요.

마찬가지로 엄마의 자식 2명도 서로 대칭을 이루기 때문에 동형적 등위성을 가집니다.

이 방법에 사용되는 제약을 더 약화시킨 것이 다음에 설명할 보편적 등위성입니다.

보편적 등위성(Regular Equivalence)

보편적 등위성은 동형적 등위성의 제약을 보다 약화시킨 것으로 "유사한 이웃을 가진 노드는 유사하다."는 개념으로 정리할 수 있습니다. 전세계의 가족들을 모아놓은 네트워크를 예로 들자면, 모든 어머니는 서로 유사하다고 보는 식이죠. 그 이유는 같은 이웃을 공유하기 때문도 아니고, 같은 수의 자식을 가져서 대칭을 이루는 것 때문도 아닙니다. 모두 "자식"이라는 유사한 이웃들을 가지고 있기 때문입니다.

그런데 "자식"들이라는 이웃이 서로 유사한지는 어떻게 알 수 있을까요? 자식들이 서로 유사한 이유 역시 유사한 이웃인 "어머니"를 가지고 있기 때문인데... 그러면 순환 논리가 되어버리는거 아닐까요?

다행히도 서로가 서로를 정의하는 현상을 수식으로 표현하면 하나의 방정식을 세울 수 있게 됩니다.

말로 풀어서 설명하자면, 노드 i와 j의 유사도는 i의 모든 이웃노드들 k에 대해서 k와 j의 유사도를 모두 합친것과 비례한다. (이때 그 비례상수는 α)

이를 행렬로 표현하면

라고 쓸수 있을텐데, 이렇게 쓰게 되면 대각행렬의 값이 정해지지 않습니다. 수식을 약간 수정해서 단위행렬을 더해주면, 대각행렬의 값이 0이 아니게 되겠죠. (모든 노드는 자기 자신과 유사하게 됨)

복잡한 문제가 단순한 행렬방정식으로 바뀌었죠. (놀라운 선형대수학의 힘) 다음과 같이하여 행렬값을 구할 수 있습니다.

실제로 어떤 값이 나올지 궁금하군요. 위의 그래프를 예시로 한번 계산해볼까요?

α값은 중심성 계산할때와 마찬가지로 최대 고윳값의 역수보다는 작은 값으로 설정해야합니다.  0.3으로 잡고 계산해볼까요.

당연하게도 대각행렬의 값들이 제일 크게 나옵니다. 대각행렬 값은 무시하고 나머지 성분중에서 큰 값들을 찾아봅시다.

2행5열의 1.303이 1위입니다. 즉 B-E가 보편적 등위성의 관점에서는 유사도 1.303로 제일 유사하다는 것을 알 수 있습니다.

지금은 작고 서로 복잡하게 얽힌 그래프를 대상으로 해서 잘 감이 안오겠지만 더 큰 그래프를 대상으로 하면 의도한 바대로 유사도를 산출해 준다는 것을 알 수 있을 것입니다.