グラフ理論入門：2つの頂点間の類似性・距離の測定方法

グラフ内の2つの頂点間の類似性・距離をどう測るか？

グラフ分析において、頂点間の距離や類似性を測る尺度には、大きく分けて「測地線距離（Geodesic Distance）」と「ランダムウォークに基づく距離」の2種類があります。

測地線距離（Geodesic Distance）

グラフ内の2つの頂点間の距離を測る最もシンプルな尺度は、頂点同士をつなぐ最短経路です。通常、2つの頂点間の測地線距離は、その最短経路を構成する辺の本数として定義されます。また、グラフ内でつながっていない2つの頂点の場合、測地線距離は無限大として表されます。

測地線距離を活用することで、グラフ分析やクラスタリングに役立つさまざまな指標を導き出せます。グラフ G = (V, E)（Vは頂点集合、Eは辺集合）が与えられたとき、以下のような指標が定義されます。

• 離心度（Eccentricity）： 頂点 v ∈ V に対して、v の離心度 eccen(v) は、v と V − {v} に属する任意の頂点 u との間の測地線距離の最大値です。離心度は、グラフ内で v が最も遠くにある頂点からどれほど離れているかを表します。

• 半径（Radius）： グラフ G の半径は、すべての頂点の離心度の最小値です。
  r = min eccen(v)、ただし v ∈ V
  半径は、グラフの「最も中心的な点」と「最も遠い境界」の間の距離を表します。

• 直径（Diameter）： グラフ G の直径は、すべての頂点の離心度の最大値です。
  d = max eccen(v)、ただし v ∈ V
  直径は、任意の2つの頂点間の最大距離を定義します。

• 周辺頂点（Peripheral Vertex）： 直径を生み出す（実現する）頂点を指します。

SimRank：ランダムウォークと構造的文脈に基づく類似性

多くの応用場面では、グラフ内の頂点間の類似性を計算するうえで、測地線距離は必ずしも適切とは言えません。そこで登場するのが SimRank です。SimRankは、ランダムウォークとグラフの根本的な構造に基づいた類似性尺度を採用しています。数学におけるランダムウォークとは、一連の確率過程を順次たどっていく軌跡のことを指します。

類似性を表現する方法としては、主に次の2つがあります。

• 構造的文脈に基づく類似性： ソーシャルネットワーク上で、2人のユーザーが同じ隣接ノード（友人）を持っている場合、両者は互いに類似しているとみなされます。この発想は非常に直感的です。共通の友人から多くの推薦を受けている2人は、似たような意思決定を下す傾向があるためです。このタイプの類似性は、頂点の局所的な構造（近傍関係）に依存しており、「構造的文脈に基づく類似性（structural context-based similarity）」と呼ばれます。

• ランダムウォークに基づく類似性： 例として、AllElectronics社がソーシャルネットワーク上のAdaさんとBobさんの両方にプロモーション情報を送信した状況を考えてみましょう。AdaさんとBobさんは、その情報をネットワーク内の自分の友人（隣接ノード）へランダムに転送できます。このとき、両者の親密さは、「Adaさん宛ての情報」と「Bobさん宛ての情報」を同じユーザーが同時に受け取る確率によって計算できます。このタイプの類似性は、ネットワーク全体でのランダムウォークの到達可能性に基づくものであり、「ランダムウォークに基づく類似性（similarity based on random walk）」と定義されます。