Preserving Personalized Pagerank in Subgraphs
-
Andrea Vattani, Deepayan Chakrabarti, Maxim Gurevich
-
ICML 2011
概要
-
既存のグラフサンプリングは、Sを計算して、G[S]を出力
-
局所的な指標は良いけど、大域的な指標は駄目
-
S={u,v}だと、N(u)∩N(u)が大きくても、微妙になる
-
辺を弄ってPPRを保持する問題
問題定式化と提案手法
-
入力: $$ G=(V,w_G), S \subseteq V $$
-
出力: $$ H=(S,w_H) $$
-
目標: $$ \pi_i^H(j) = \pi_i^H(j) \forall i, j \in S $$
-
※クラシカルにはH=G[S]で、PPRの値の差の最小化だが、これはNP-hard
-
問題: (Gによっては)そんなHを作れないことがある
-
解決法: SINKを作る
-
アルゴリズムNodeRemoval
-
V-Sの頂点zを(適当な順で)削除
-
$$ x, y \in N(z) $$について
-
$$ w_H(x,y), w_H(x, \mathrm{sink}) $$を割り当てる
-
利点: 厳密にPPRを保持する
-
欠点: Sが小さい時に辺数がやばお
-
解決法: 疎化
-
Weighted: wH(u,v)<τなら、(u,v)を消して(u,SINK)に割り振る
-
Unweighted: Weightedの結果の重みを無くす
-
グローバルPageRankの保持…SOURCEを作って頑張る(省略)
実験
まとめ
-
そこそこ良さそう?
-
辺重みを自由に変えられるので自由度が高そう
-
誤差がτなのは良いか分からん
ICML PageRank 疎化
2016/12/12
最終更新:2016年12月12日 19:22