Efficient Algorithms for Public-Private Social Networks
-
Flavio Chierichetti, Alessandro Epasto, Ravi Kumar, Silvio Lattanzi, Vahab Mirrokni
-
KDD 2015
概要
-
ベストペーパー
-
ユーザ毎に「公開ネットワーク∪ユーザの秘匿ネットワーク」で問題を解きたい
-
めっちゃ色々な問題に対して考えたよ
動機付け
-
ソーシャルネットワーク上のプライバシー(の例)
-
ユーザが友達をプライベートに設定
-
ユーザがプライベートグループを作る
-
証拠
-
Facebook(一部)で半分位の友達リストが隠れてた
-
だから,提供者が公開ネットワークだけを使って推薦した場合はしょぼそう
-
「公開ネットワーク∪ユーザの秘匿ネットワーク」でやりたい,遅い!
ヤりたいこと
-
G: 公開ネットワーク
-
G_u: ユーザuの秘匿ネットワーク
-
ある問題について
-
Gに前処理をすることで,
-
G∪G_u上の問題を効率的に解く
スケッチ手法
-
到達可能頂点数
-
近接中心性
-
All-distances sketches, revisited: HIP estimators for massive graphs analysis
-
証明は煩雑だけど,なんとか出来そう
標本手法
-
全点対間最短経路
-
Personalized PageRank
-
social affinity
-
Correlation clustering
実験
-
|V|<4M, |E|<120M
-
秘匿ネットワークはStarかClique
-
基本的に愚直との速度比を測定,100万倍位はやい
まとめ
-
これでベストペーパーなのかあ
-
そういう(2-hopとか)データの出すか,
-
こういうモデルだと推薦の質がよくなるか,
-
すごく汎用的・統一的な手法
-
を期待していた…
KDD
2015/08/20 17:26
最終更新:2015年08月20日 17:30