読者です 読者をやめる 読者になる 読者になる

Debuginfo

思考とアウトプット

グラフ理論::SimRank

グラフが関係するサービスを開発しようと考えているので、まずオーソリティな論文を読んでみた。


SimRank: A Measure of Structural-Context Similarity - Glen Jeh, Jeniffier Widom




肝はこれ。再帰で書けば答えがでるはず? と思って実装したら無限ループしてしまいました。
グラフにCycleがあるとループしてしまう(コードを読めば当たり前でした(^^;;)
4.4.1を読んでみると、あれ?これ再帰じゃないじゃん。再帰ではなくループで収束させるみたい。
下記がアルゴリズムでした。





Graphモジュールを使って書いてみました。昨日使い始めたgit/github/gistで :)


ノードの類似度が有向グラフ情報だけで出せるのは興味深い。オーダはO(n^2)。
論文の例のようにAさんとBさんが買物をしたときに、グラフ化してその類似度を出せる。いいねー。


グラフの用語

  • X -> YのDirected edgeの場合、Successor : Y, Predecessor : X と呼ぶ。
  • Strongly connected - 強連結 : Directed graphで任意の点から任意の点への有効道が存在するとき、グラフは強連結であるという。
  • Biconnected graph - http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L25-Connectivity.htm : A graph is biconnected, if there are no vertices whose removal will disconnect the graph. つまり、ノードをなくしてもグラフが切断されないグラフのこと(だと理解)