Efficient core decomposition in massive networks

James Cheng, Yiping Ke, Shumo Chu, and M. Tamer Ozsu. 2011. Efficient core decomposition in massive networks. In Proceedings of the 2011 IEEE 27th International Conference on Data Engineering (ICDE '11). IEEE Computer Society, Washington, DC, USA, 51-62. DOI=10.1109/ICDE.2011.5767911 http://dx.doi.org/10.1109/ICDE.2011.5767911

  • 問題
    • グラフを core-decomposition したい
      • k-core とは: largest subgraph of G in which every vertex set has degree >= k
      • core decompositio: k-core for all k
    • 普通にやるのは超簡単，線形時間．わかるべ．
    • でもランダムアクセセスがちょっとやばい．on-disk で動くようにしたい．
  • アルゴリズム
    • 長すぎ
    • 普通のアプローチを bottom-up と呼ぶのに対してこれを top-down と呼んでいる
    • graph partitioning を行って，メモリに部分グラフを載せて何かをするっぽい
    • 計算量，最悪で O(kmax(m+n) / B) IO とか言ってる
  • 実験結果
    • 53M vertices / 1.7B edges の Web Graph で 2000 秒
    • プラクティカルな速度だとは思うが，普通のアルゴリズムをディスクに載せたときどのぐらい遅くなるのか知りたいなあ (使い物にならない？)
    • 実験結果からはプラクティカルには最悪計算量より O((m+n)/B) っぽいとか言っているのでやっぱヒューリスティクス

感想

よく見ると，2 年前の SIGMOD の maximal clique の on-disk のアルゴリズムをやってる人だ…と思ったら VC-Index もこの人やん．

on-disk のアルゴリズムをガンガン考える人みたいな感じなのか，ぱない!!

一方で枝数が数 B のグラフとか本当はちょっと良いマシンなら別にメモリに載るだろという気もしなくもないし，今その辺にあるデータセットで枝数が 10B 超えてる物はみたことがない．

on-disk 系のアルゴリズムこういうのは cache-oblivious とかにできるともっと格好いいがむずいかな〜．そもそもグラフの cache-oblivious なアルゴリズムはあるのか？

…と思ったらこれとか出てきた． Erik D.Demaine やん． http://erikdemaine.org/papers/BufferTrees_STOC2002/paper.pdf