グラフ理論::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. つまり、ノードをなくしてもグラフが切断されないグラフのこと(だと理解)