On Compressing Social Networks

On Compressing Social Networks

  • Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, Prabhakar Raghavan
  • KDD 2009

概要

  • ウェブグラフの圧縮は既にある
    • 平均3bits
  • ソーシャルネットワークの場合は?
  • 問題を定式化、NP-hardだけど適当にヒューリスティクスで頑張る

ウェブグラフの圧縮

Compression-friendly ordering

問題定式化

  • MLogA $$ \sum_{(u,v) \in E}\lg|\pi(u)-\pi(v)| $$
  • MLogGapA $$ \sum_{u \in V}f_\pi(u, N^+(u)) $$
    • $$ f_\pi(u, N^+(u)) = \sum_{i}\lg|\pi(u_i)-\pi(u_{i-1})| $$
    • 隣接リスト表現を考えて隣り合う点対のコストを考える
  • 両方夜もNP-hard
  • expander-likeだと圧縮しにくい

ヒューリスティクス

  • 出近傍のMinHashでソート(Jaccard係数が大きければ近くにする)
  • Preferential attachmentで正当化つき

実験

  • 色々やりました

まとめ

  • 良い論文

KDD グラフ圧縮

2017/06/11

タグ:

KDD グラフ圧縮
最終更新:2017年06月11日 00:42