그래프 이론에서 정점(vertex) 간의 거리와 유사성을 측정하는 방법은 크게 두 가지로 나눌 수 있습니다. 하나는 최단 경로를 기반으로 하는 지오데식 거리(Geodesic Distance)이고, 다른 하나는 랜덤 워크(Random Walk)에 기반한 거리입니다.
지오데식 거리(Geodesic Distance)
그래프에서 두 정점 사이의 거리를 측정하는 가장 간단한 방법은 두 정점을 연결하는 최단 경로의 길이입니다. 일반적으로 두 정점 간의 지오데식 거리는 최단 경로를 구성하는 변(edge)의 개수로 정의됩니다. 그래프에서 서로 연결되어 있지 않은 두 정점의 경우, 지오데식 거리는 무한대(∞)로 표현됩니다.
지오데식 거리를 활용하면 그래프 분석과 클러스터링에 유용한 다양한 척도를 정의할 수 있습니다. 정점의 집합 V와 변의 집합 E로 이루어진 그래프 G = (V, E)가 주어졌을 때, 다음과 같은 척도들을 정의할 수 있습니다.
편심도(Eccentricity) — 정점 v ∈ V에 대해 v의 편심도 eccen(v)는 v와 v를 제외한 임의의 정점 u ∈ V − {v} 사이의 지오데식 거리 중 최댓값입니다. 편심도는 그래프 안에서 v가 가장 먼 정점으로부터 얼마나 떨어져 있는지를 나타냅니다.
반지름(Radius) — 그래프 G의 반지름은 모든 정점의 편심도 중 최솟값입니다.
r = min eccen(v), v ∈ V
반지름은 그래프의 '가장 중심에 있는 점'과 '가장 먼 경계' 사이의 거리를 의미합니다.지름(Diameter) — 그래프 G의 지름은 모든 정점의 편심도 중 최댓값입니다.
d = max eccen(v), v ∈ V
지름은 임의의 두 정점 쌍 사이에서 가능한 최대 거리를 정의합니다.주변 정점(Peripheral Vertex) — 그래프의 지름을 만들어내는 정점을 주변 정점이라고 합니다.
SimRank — 랜덤 워크 및 구조적 맥락 기반 유사성
여러 실제 응용 분야에서는 지오데식 거리만으로 그래프 내 정점 간의 유사성을 계산하기에 적합하지 않은 경우가 많습니다. SimRank는 랜덤 워크와 그래프의 근본적인 구조에 기반한 유사성 척도입니다. 수학적으로 랜덤 워크(random walk)란 연속적인 무작위 과정을 거치며 형성되는 궤적을 의미합니다.
유사성을 표현하는 대표적인 방법은 다음의 두 가지입니다.
1. 구조적 맥락 기반 유사성(Structural Context-Based Similarity)
소셜 네트워크에서 두 사용자가 동일한 이웃을 가지고 있다면, 두 사용자는 서로 유사하다고 간주합니다. 이러한 휴리스틱은 직관적으로 타당합니다. 공통 친구들로부터 비슷한 추천을 받은 두 사람은 유사한 결정을 내리는 경향이 있기 때문입니다. 이처럼 정점의 국소 구조, 즉 이웃 관계에 의존하는 유사성을 구조적 맥락 기반 유사성이라고 합니다.
2. 랜덤 워크 기반 유사성(Similarity Based on Random Walk)
AllElectronics가 소셜 네트워크상에서 Ada와 Bob에게 홍보 정보를 발송했다고 가정해 봅시다. Ada와 Bob은 해당 정보를 네트워크 안의 자신들의 친구(또는 이웃)에게 무작위로 전달할 수 있습니다. 이때 Ada와 Bob 간의 친밀도는, 처음에 Ada와 Bob에게 보내진 홍보 정보를 다른 사용자가 동시에 수신할 확률로 계산할 수 있습니다. 이러한 유사성은 네트워크 전체에서의 랜덤 워크 도달 가능성(reachability)에 의존하므로, 랜덤 워크 기반 유사성이라고 정의합니다.