측지 거리와 임의 보행을 기반으로 한 거리와 같은 두 가지 유형의 측정이 있습니다.
측지 거리 − 그래프에서 두 꼭짓점 사이의 거리를 간단히 측정하면 꼭짓점 사이의 최단 경로가 됩니다. 일반적으로 두 꼭짓점 사이의 측지 거리는 꼭짓점 중 최단 경로의 여러 변으로 환산한 길이입니다. 그래프에서 연결되지 않은 두 정점의 경우 측지 거리는 무한대로 표시됩니다.
측지 거리를 활용하여 그래프 분석 및 클러스터링을 위한 다양한 유용한 측정값을 나타낼 수 있습니다. 그래프 G =(V, E)가 주어지면 V는 꼭짓점의 집합이고 E는 모서리의 집합이며 다음을 나타낼 수 있습니다. -
-
정점 v ∈ V의 경우, eccen(v)로 표시된 v의 이심률은 v와 여러 정점 u ∈ V − {v} 사이의 가장 높은 측지 거리입니다. v의 이심률은 v가 그래프의 끝 정점에서 얼마나 멀리 떨어져 있는지를 캡처합니다.
-
그래프 G의 반지름은 모든 꼭짓점의 최소 이심률입니다.
-
즉, r =min eccen(v)
v ∈ V
반경은 그래프의 "가장 중심점"과 "가장 먼 경계선" 사이의 거리를 캡처합니다.
-
그래프 G의 지름은 모든 정점의 최대 편심입니다.
-
즉, d =최대 eccen(v)
v ∈ V
지름은 정점 쌍 사이의 가장 높은 거리를 정의합니다.
-
주변 꼭짓점은 지름을 생성하는 꼭짓점입니다.
SimRank - 랜덤 워크 및 구조적 맥락을 기반으로 한 유사성 − 다양한 응용에서 측지 거리는 그래프의 꼭짓점 간의 유사도를 계산하는 데 부적절할 수 있습니다. SimRank에서 유사도 측정은 랜덤 워크와 그래프의 기본 프레임워크에 따라 달라집니다. 수학에서 랜덤 워크는 연속적인 랜덤 프로세스를 포함하는 궤적입니다.
다음과 같은 유사성을 나타내는 두 가지 방법이 있습니다 -
-
두 명의 사용자가 소셜 웹에서 동일한 이웃이 있는 경우 서로 동일하게 취급됩니다. 많은 수의 공통 친구로부터 추천을 받는 두 사람이 동일한 결정을 내리기 때문에 이 휴리스틱은 지각적입니다. 이러한 유형의 유사성은 정점의 로컬 구조(예:이웃)에 따라 달라지며 구조적 컨텍스트 기반 유사성으로 알려져 있습니다.
-
AllElectronics가 소셜 웹에서 Ada와 Bob 모두에게 판촉 데이터를 보낸다고 가정합니다. Ada와 Bob은 이러한 데이터를 네트워크의 친구(또는 이웃)에게 무작위로 전달할 수 있습니다. Ada와 Bob 사이의 친밀도는 처음에 Ada와 Bob에게 전송된 프로모션 데이터를 다른 사용자가 동시에 수신할 가능성으로 계산할 수 있습니다. 이러한 유형의 유사성은 웹을 통한 랜덤 워크 도달 가능성에 따라 달라지므로 랜덤 워크를 기반으로 한 유사성으로 정의됩니다.