「Streaming Algorithms for k-core Decomposition」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
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があって…ってなる
- アルゴリズム
++ δ(v)=deg(v)
++ δの昇順ソート
++ 今ポップしたvについてK(v)=δ(v)
++ vに隣接する頂点wについて
--- δ(w)>δ(v)ならδ(w)--
++ ↑の操作後もδの昇順は守る
* 色々便利な定理
- 細々と定理を証明していく
- でっていう？
- 辺uvが挿入/削除された時
- K(u)<=K(v)の時だけK(u)は変化する
- uを根としてK(w)=K(u)となるwについてBFSして得られた頂点集合だけがKが変わりうる
* アルゴリズム
** Subcore アルゴリズム
- 愚直にKが変わりうる頂点を全部とってくる
** Purecore アルゴリズム
- ↑の頂点集合を次数とかでもっと制限する
** The Traversal Algorithm
- さらにさらに制限する
* 実験
** データセット
- サイズ色々、平均次数、最大次数も色々
- purecoreのサイズがどうなるかーとかも調べている
** 結果
- max10^4倍速いといっている
-- はい
* まとめ
- 何かすでにありそうだけどそうでもないのかな？
- 計算量は特に議論しないのね
-- 調べる（？）頂点数が減ればいいのかな
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があって…ってなる
- アルゴリズム
++ δ(v)=deg(v)
++ δの昇順ソート
++ 今ポップしたvについてK(v)=δ(v)
++ vに隣接する頂点wについて
--- δ(w)>δ(v)ならδ(w)--
++ ↑の操作後もδの昇順は守る
* 色々便利な定理
- 細々と定理を証明していく
- でっていう？
- 辺uvが挿入/削除された時
- K(u)<=K(v)の時だけK(u)は変化する
- uを根としてK(w)=K(u)となるwについてBFSして得られた頂点集合だけがKが変わりうる
* アルゴリズム
** Subcore アルゴリズム
- 愚直にKが変わりうる頂点を全部とってくる
** Purecore アルゴリズム
- ↑の頂点集合を次数とかでもっと制限する
** The Traversal Algorithm
- さらにさらに制限する
* 実験
** データセット
- サイズ色々、平均次数、最大次数も色々
- purecoreのサイズがどうなるかーとかも調べている
** 結果
- max10^4倍速いといっている
-- はい
* まとめ
- 何かすでにありそうだけどそうでもないのかな？
- 計算量は特に議論しないのね
-- 調べる（？）頂点数が減ればいいのかな
&tags()
&update()
