Catching the head, tail, and everything in between: a streaming algorithm ...

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} $$
  • パラメータ
    • $$ p_h, p_t $$
  • 記述
  1. $$(u,v)$$を受け取る
  2. uとvについてそれぞれ以下を実行
    1. if $$ v \in S_h $$
      • $$\mathrm{ct}_h(v)$$をインクリメント
    2. o.w.
      • 確率$$p_h$$で頂点vを$$S_h$$に追加
      • $$\mathrm{ct}_t(v) \leftarrow 1$$
    3. if $$ v \in S_t $$
      • $$\mathrm{ct}_t(v)$$をインクリメント
    4. 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) $$
    • Cは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')の相対誤差がδ以内
    • 近いd'ってしないとあまり上手くないはず
  • 一番大きい$$ (\epsilon, \epsilon) $$-closeを距離とする

実験

  • 最大でOrkut
  • Relative Hausdorff 距離で見ると提案手法が圧倒的に安定している

まとめ

  • p_h, p_tの設定が難しそう?
  • 解析が会議版では無いので,長いやつを見たほうが良さそう

ICDM ストリームアルゴリズム 次数分布

2016/02/15

最終更新:2016年02月16日 00:55