Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks
WWW 2011
目的
- メインメモリに載せたい，隣接リストを高速に取得できるようにしたい
既存手法 (BV)
- 頂点をいいかんじに並べる（similarity, locality）
- 隣接点が似ている頂点との差分で覚える (copying)
- 頂点番号の差分で覚える (gap strategy)
- など
問題点
頂点の並べ方が重要
- Web Graph: URL でソートすればいいｗ 高性能
- Social Network: 性能が出ない
提案手法
コミュニティ検出手法を使おう！クラスタ内の頂点は似ているはず．
並べるアルゴリズム
今の順番がある．ランダムな適当なリソリューションでやって，代表元をとってそれのもとのじゅんでならびかえる．
実験結果
良くなった．既存の手法は，頂点の元の順番に意味があることを利用してしまっていた．
ウェブグラフははるかに簡単で，ソーシャルは難しい．ソーシャルでも，Co-authorやHollywoodみたいなクリークが多い感じのネットワークでは簡単．
でも結局，3倍とかにしか圧縮しかできなくて，それのために十倍とか百倍とか遅くなるのは，許せるのか？
