SimRank: A Measure of Structural-Context Similarity

"SimRank: A Measure of Structural-Context Similarity" という論文を読んだので内容をメモ。

• オブジェクトとオブジェクトの関係から類似度を測りたい
  • 関係というのは、例えば、論文の引用関係とか、Webページのリンク、被リンクの関係など
• 「2つのオブジェクトが関係しているオブジェクトが似ていれば、その2つのオブジェクトは似ている」と仮定
  • A, A', B, C という4つの論文があり、AはBを引用し、A'はCを引用しているとする。ここでAとA'が似ているとすると、BとCも似ているはず。
• SimRankというドメインに依らない尺度を導入して、類似度を測ってみる

モデル

2つのオブジェクト a, b に対して、類似度 s(a, b) を次のように定義する。

つまり、a, b の類似度は、a と b に入ってくる辺の始点のオブジェクトの類似度の平均を C 倍したものである。C は 0 から 1 の間の実数であり、類似性の減少率を表す。この定義が再帰的な定義であることに注意。s(a, b) は常に存在し、一意であることが示せる。

計算方法

ナイーブな方法

上の類似度の定義をすべての頂点の対に対して収束するまで反復的に計算する。

まず、次のように初期化する。

後は次の漸化式を使って更新していく。

この漸化式で k → ∞ とするとSimRankの類似度の式に一致する。実際には k = 5 ぐらいまで計算すれば十分であることが実験的に示されている。

枝狩り

グラフ上で遠いオブジェクトの類似度を 0 としてしまうことで計算量を減らせる。