Streaming Graph Partitioning for Large Distributed Graphs - todo314 @ ウィキ

Streaming Graph Partitioning for Large Distributed Graphs

• Isabelle Stanton, Gabriel Kliot
• In KDD 2012

メモ

• セミナー
• K.Inabaさん

問題

• 巨大グラフを複数に分割したい
• ストリーミングアルゴリズムじゃないと意味ないお
• 入力
  • G(V,E)
  • k: マシン台数
  • ε: アンバランス度
• 出力
  • V1, V2, …, Vk
  • $$ |Vi| \leq \frac{(1+\epsilon)|V|}{k} $$
  • または
  • $$ \sum \deg(V_i) \leq (1+\epsilon)\sum \deg(v)/k $$
  • を満たすようにする
• 目標
  • cross edge数を最小化
  • $$ \mbox{minimize} |\{(u, v) \in E \mid id[u]id[v]\}| $$
    • idは所属パーティション

ストリーム順番

• DFS
• BFS
  • 無理じゃね？
• RANDOM

パーティション番号割り当て

• vが来たらすぐにパーティション番号を決定
• vの近傍だけ見て良い

ヒューリスティクス

• Deterministic Greedy（これがよかったらしい）
  • 近傍に多いパーティションを選ぶ
  • あと何か色々
  • 多すぎわろた

実験

データセット

• ソーシャル，合成
• LiveJournal, Twitter以外小さい…

cross-edge

• small-worldじゃないの
  • Randomが悪い
  • というかBFSが良い

計算速度

• PageRank計算のパフォーマンス
• cross-edge少ないほうが速いよ

• k分割したいなら，ストリーミングでk個のコミュニティを検出することに…
• 実質Twitterだけだよね～（データセット）

KDD graph partitioning streaming algorithm

2013-10-17 23:30:26 (Thu)