Efficient Algorithms for Public-Private Social Networks

Efficient Algorithms for Public-Private Social Networks

  • Flavio Chierichetti, Alessandro Epasto, Ravi Kumar, Silvio Lattanzi, Vahab Mirrokni
  • KDD 2015

概要

  • ベストペーパー
  • ユーザ毎に「公開ネットワーク∪ユーザの秘匿ネットワーク」で問題を解きたい
  • めっちゃ色々な問題に対して考えたよ

動機付け

  • ソーシャルネットワーク上のプライバシー(の例)
  • ユーザが友達をプライベートに設定
    • そのユーザ-友達間の辺はそのユーザにしか見えない
  • ユーザがプライベートグループを作る
    • クリークがグループ外からは見えない
  • 証拠
    • Facebook(一部)で半分位の友達リストが隠れてた
  • だから,提供者が公開ネットワークだけを使って推薦した場合はしょぼそう
  • 「公開ネットワーク∪ユーザの秘匿ネットワーク」でやりたい,遅い!

ヤりたいこと

  • G: 公開ネットワーク
  • G_u: ユーザuの秘匿ネットワーク
    • uから2-hopしか無いとする
  • ある問題について
  • Gに前処理をすることで,
    • poly(m)
  • G∪G_u上の問題を効率的に解く
    • |E_u|+poly(log n)

スケッチ手法

  • 到達可能頂点数
    • bottom-k sketchをうまうこと使う
  • 近接中心性
    • 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

タグ:

KDD
最終更新:2015年08月20日 17:30