On Compressing Social Networks
-
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, Prabhakar Raghavan
-
KDD 2009
概要
-
ウェブグラフの圧縮は既にある
-
ソーシャルネットワークの場合は?
-
問題を定式化、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
最終更新:2017年06月11日 00:42