グラフ内の2つの頂点間の類似性または距離をどのように測定できますか？

測地線距離とランダムウォークに基づく距離など、2種類の測定値があります。

測地線距離 −グラフ内の2つの頂点間の距離の簡単な測定値は、頂点間の最短ルートです。通常、2つの頂点間の測地線距離は、頂点間の最短経路の多重辺に関する長さです。グラフでリンクされていない2つの頂点の場合、測地線距離は無限として表されます。

測地線距離を利用することで、グラフ分析やクラスタリングに役立つさまざまな測定値を表すことができます。グラフ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 =max eccen（v）

  v∈V

  直径は、頂点のいくつかのペア間の最大距離を定義します。

• 周辺頂点は、直径を生成する頂点です。

SimRank-ランダムウォークと構造コンテキストに基づく類似性 −さまざまなアプリケーションでは、グラフ内の頂点間の類似性を計算する際に測地線距離が不適切になる可能性があります。 SimRankでは、類似度はランダムウォークとグラフの基本的なフレームワークに依存します。数学では、ランダムウォークは連続するランダムプロセスを取ることを含む軌道です。

類似性を表すには、次の2つの方法があります-

• ソーシャルウェブに同じ隣人がいる場合、2人のユーザーは互いに同じように扱われます。多数の一般的な友人から推奨を受け取った2人が同じ決定を行うため、このヒューリスティックは知覚的です。このタイプの類似性は、頂点のローカル構造（つまり、近傍）に依存し、構造コンテキストベースの類似性として知られています。

• AllElectronicsがソーシャルウェブのAdaとBobの両方にプロモーションデータを送信するとします。 AdaとBobは、そのようなデータをネットワーク内の友人（または隣人）にランダムに転送できます。 AdaとBobの間の近さは、異なるユーザーがAdaとBobに最初に送信されたプロモーションデータを同時に受信する可能性によって計算できます。このタイプの類似性は、Webを介したランダムウォークの到達可能性に依存するため、ランダムウォークに基づく類似性として定義されます。