Fast Single-Pair SimRank Computation
-
Pei Li, Hongyan Liu, Jeffrey Xu Yu, Jun He, Xiaoyong Du
-
SDM 2010
概要
-
全点対間SimRankはあるけど、クエリしたいよねー
-
ペアのSimRankを高速に計算するよ
-
精度を落とさずにやったね
SimRank
-
一般的には下の式を収束するまで反復
-
$$ R_{k+1}(a,b) = \frac{C}{|I(a)||I(b)|}\sum_{i \in I(a)}\sum_{j \in I(b)}R_k(i,j) $$
-
行列でも書ける
-
Q. SimRankってそもそも何だ?
-
A. 2人が出会うまでのランダムウォーク
-
M_k(a,b): kステップ目で最初にである確率
-
R_k(a,b)はM_iの和で表される
提案手法
-
M_k(a,b)を頑張って計算していくスタイル
-
kの最大値は…?
-
絶対誤差をΔとすると、K=floor(log_C Δ)
-
パスで考えよう
-
パスを決定すると、それを辿る確率は簡単に計算できる
-
a/bから出発した長さkのパスが最後でだけ一致する(初めて出会う)なら
-
そういうパスの出現確率を計算してM_k(a,b)に足す
A Naive Path-Tree Matching Method
-
G=(V,E), C, (a,b), kが与えられる
-
a,bから出発する長さkのパスを列挙する
-
2つのパスをループ
-
最後だけ一致するパスのペアを見つけ、出現確率の和をとってかえす
A New Single-Pair SimRank Method
-
流石に遅すぎる
-
Position Matrix P_k^{ab}
-
(i,j)成分は、kステップ目で、a/bがi/jにいる確率を表す
-
P_k^{ab}
-
P_k^{ab}で、kより前では2人は合っていない状態だけ考慮する
-
直感的に$$ M_k(a,b) = \sum_i (\tilde{P}_k^{ab})_{ii} $$
-
この行列を頑張って計算する
-
後なんか適当に速くする
実験
-
データセットは小さめ
-
手法(最後2つは高速化
-
SimRank: All-pair
-
NSP: naive Single-Pair SimRank
-
ISP: iterative Single-Pair SimRank
-
AR: Access Reduction
-
TF: Threshold Filtering
-
Threshold Filteringというのをしないとちょっと遅い
-
6反復くらいで十分???
-
大体100倍位速い
まとめ
-
関係ないけどSimRankの意味が分かって良かった
-
100倍ってどうなんでしょう?
-
そう考えると1対全の方が需要ありそう
-
計算量評価があんまりタイトじゃないなあ…
SDM SimRank
2013-11-13 23:51:05 (Wed)
最終更新:2013年11月13日 23:51