Streaming Graph Partitioning for Large Distributed Graphs
-
Isabelle Stanton, Gabriel Kliot
-
In KDD 2012
メモ
問題
-
巨大グラフを複数に分割したい
-
ストリーミングアルゴリズムじゃないと意味ないお
-
入力
-
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]\}| $$
ストリーム順番
パーティション番号割り当て
-
vが来たらすぐにパーティション番号を決定
-
vの近傍だけ見て良い
ヒューリスティクス
-
Deterministic Greedy(これがよかったらしい)
-
近傍に多いパーティションを選ぶ
-
あと何か色々
-
多すぎわろた
実験
データセット
-
ソーシャル,合成
-
LiveJournal, Twitter以外小さい…
cross-edge
計算速度
-
PageRank計算のパフォーマンス
-
cross-edge少ないほうが速いよ
-
k分割したいなら,ストリーミングでk個のコミュニティを検出することに…
-
実質Twitterだけだよね~(データセット)
KDD graph partitioning streaming algorithm
2013-10-17 23:30:26 (Thu)
最終更新:2013年10月17日 23:30