Streaming Algorithms for k-core Decomposition - todo314 @ ウィキ

Streaming Algorithms for k-core Decomposition

• Ahmet Erdem Saríyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, Ümit V. Çatalyürek
• VLBD 2013

概要

• k-core decompositionあるよねー
• 実際は、辺が挿入されたり削除されたりするから、そういう走査サポートしたいよねー
• 作りました
• 実験しました
  • 毎回batchするより断然良い

k-core decomposition

• K(v): vが属せるk-coreのうち最大のk
  • 基本的に、周りに1があって、中に2があって、その内側に3があって…ってなる
• アルゴリズム
  1. δ(v)=deg(v)
  2. δの昇順ソート
  3. 今ポップしたvについてK(v)=δ(v)
  4. vに隣接する頂点wについて
     • δ(w)>δ(v)ならδ(w)--
  5. ↑の操作後もδの昇順は守る

色々便利な定理

• 細々と定理を証明していく
• でっていう？
• 辺uvが挿入/削除された時
• K(u)<=K(v)の時だけK(u)は変化する
• uを根としてK(w)=K(u)となるwについてBFSして得られた頂点集合だけがKが変わりうる

アルゴリズム

Subcore アルゴリズム

• 愚直にKが変わりうる頂点を全部とってくる

Purecore アルゴリズム

• ↑の頂点集合を次数とかでもっと制限する

The Traversal Algorithm

• さらにさらに制限する

実験

データセット

• サイズ色々、平均次数、最大次数も色々
• purecoreのサイズがどうなるかーとかも調べている

結果

• max10^4倍速いといっている
  • はい

まとめ

• 何かすでにありそうだけどそうでもないのかな？
• 計算量は特に議論しないのね
  • 調べる（？）頂点数が減ればいいのかな

VLDB k-core decomposition streaming algorithm

2013-11-13 02:27:07 (Wed)