On the Streaming Complexity of Computing Local Clustering Coefficients - todo314 @ ウィキ

On the Streaming Complexity of Computing Local Clustering Coefficients

• Konstantin Kutzkov, Rasmus Pagh
• WSDM 2013

概要

• ワンパスでlocal clustering coefficientを求めたい
  • ローカルなので、頂点ごと
  • 辺リストが任意の順でもらえる

1. 全く三角形が無い or 1/2以上のCCを持つ次数2d以上の頂点がある、かをある程度の確率でワンパスで判定するためにはΩ(m/d)ビット必要
2. ↑の限界にマッチした乱択アルゴリズムを考案

Lower bound

• Theorem 1
• ワンパス乱択アルゴリズムが

1. 次数2dの頂点はクラスタ係数0
2. クラスタ係数1/2位上の次数2dの頂点が存在する

• を1/3以上の確率で正しく区別するためにはΩ(m/d)bit以上を必要とする

One pass algorithm

準備1

• 各辺を確率pでサンプリングする
• ↑で出来たグラフについてクラスタ係数をもとめる
• 頂点v、三角形<u,v,w>について
• (u,v,w)が残る確率: p^2
• <u,v,w>が残る確率: p^3
• ∴サンプルで求めたクラスタ係数に1/pをかければ期待値では真のクラスタ係数に一致する
• サンプルには精度が必要、でもpがでかいと空間計算量がやばい、トレードオフ～

準備2

• (u,v,w)を一杯とってくる
• (u,w)はあるかしら？
• ↑は3パスで可能

提案手法

• ↑のを組み合わせてワンパス
• monochromatic sampling
• 各頂点を適当に彩色
• 端点が同色な辺だけとってくる
• 何がうれしいの？
  • もし、(u,v)と(v,w)があったら(u,w)もサンプルしたはず、無ければ、そもそも(u,w)は存在しない
  • つまり、<u,v,w>も(u,v,w)もサンプルする確率が同じ
• 彩色方法
  • 単純にfloor(C f(u))するだけ（fは適当な[0,1]関数）
• SparsifyGraph
  • 各辺が同色だったら捕獲、しきい値t以上になったら失敗
• CheckTwoPaths
  • SparsifyGraphでサンプルしたグラフについて行う
  • 次数2以上の頂点vについて、2つの近傍u,wをとってくる
  • (u,w)があったらvに関するindicator X_△(v)=1、そうじゃなかったらX_△(v)=0
  • 上手くサンプルした頂点について(v, X_△(v))を返す
• EstimateClusteringCoefficients
  • K並列でCheckTwoPathsを実行
  • ↑ので(v, X_△(v))があったらvのwedgeをp_v++
  • さらにX_△(v)なら三角形をt_v++
  • (v, t_v/p_v)を返す
• 細かなパラメータ
  • K=4/(αε^2) * log(n/δ)
  • t=9m/d
  • C=d/4
  • これで、各頂点について(ε,δ)近似

実験

• 比較方法に色々使っていて面白い
  1. 平均相対誤差
  2. Pearson相関係数
  3. Spearman 順位相関係数
• どうも真の値と近似値にはかなりの開きがあるように見える(´・ω・`)
• 大体数百並列している感じ
• ちょっと結果もはしょっている
• 主張:
• 次数分布が歪んでいると推定が良い
• 近似が辺でもまぁ、相関はある

まとめ

• アルゴリズムはちょっとおもしろいかも
• ただ、CheckTwoPathsは各頂点について1回しかwedgeを確かめないので勿体無い気がした
• 相関はちょー適当な推定でも出る気がするのであんまり参考にならなさそう
  • 次数でとかね？

WSDM clustering coefficient streaming algorithm

2014-01-23 16:58:39 (Thu)