Catching the head, tail, and everything in between: a streaming algorithm for the degree distribution
-
Olivia Simpson, C. Seshadhri, Andrew McGregor
-
ICDM 2015
概要
-
ストリームで次数分布を求めたい
-
普通にやると,tail部分の精度が酷いことに(というか破滅)なる
-
head/tailそれぞれに推定器を用意
-
Relative Hausdorff距離というナイスな距離を導入
-
実験では↑で評価→良
アルゴリズム
-
各辺が任意の順番にワンパスで来る
-
n,mは知らない(というか不定)
-
辺削除/繰り返しは無し
-
持つもの
-
$$ S_h $$: head用の頂点集合
-
$$ S_t $$: tail用の頂点集合
-
$$ \mathrm{ct}_h S_h \rightarrow \mathbb{N} $$
-
$$ \mathrm{ct}_t S_t \rightarrow \mathbb{N} $$
-
パラメータ
-
記述
-
$$(u,v)$$を受け取る
-
uとvについてそれぞれ以下を実行
-
if $$ v \in S_h $$
-
$$\mathrm{ct}_h(v)$$をインクリメント
-
o.w.
-
確率$$p_h$$で頂点vを$$S_h$$に追加
-
$$\mathrm{ct}_t(v) \leftarrow 1$$
-
if $$ v \in S_t $$
-
$$\mathrm{ct}_t(v)$$をインクリメント
-
o.w.
-
確率$$p_t$$で頂点vを$$S_h$$に追加m
-
$$\mathrm{ct}_t(v) \leftarrow 1$$
-
ポイントは,headは頂点を確率的にとっておいて,
-
tailは辺毎に確率的にとっておくこと(つまり高次数の方が残る)
-
headの推定: $$ \mathrm{C}_h(r) / p_h $$
-
tailの推定: $$ \mathrm{C}_t(r - \ell(r)) / (1-(1-p_t)^r) $$
-
$$ d_{thr} $$というパラメータ(具体的に計算可)を境にhead/tailを使い分ける
解析
-
空間使用量: $$ O(p_h n + p_t m) $$
Relative Hausdorff 距離
-
分布F,Gが$$ (\epsilon, \delta) $$-closeとは…
-
各dについて,近いd'があって,F(d)とG(d')の相対誤差がδ以内
-
一番大きい$$ (\epsilon, \epsilon) $$-closeを距離とする
実験
-
最大でOrkut
-
Relative Hausdorff 距離で見ると提案手法が圧倒的に安定している
まとめ
-
p_h, p_tの設定が難しそう?
-
解析が会議版では無いので,長いやつを見たほうが良さそう
ICDM ストリームアルゴリズム 次数分布
2016/02/15
最終更新:2016年02月16日 00:55