「On the Streaming Complexity of Computing Local Clustering Coefficients」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* On the Streaming Complexity of Computing Local Clustering Coefficients
- Konstantin Kutzkov, Rasmus Pagh
- WSDM 2013
* 概要
- ワンパスでlocal clustering coefficientを求めたい
-- ローカルなので、頂点ごと
-- 辺リストが任意の順でもらえる
+ 全く三角形が無い or 1/2以上のCCを持つ次数2d以上の頂点がある、かをある程度の確率でワンパスで判定するためにはΩ(m/d)ビット必要
+ ↑の限界にマッチした乱択アルゴリズムを考案
* Lower bound
- Theorem 1
- ワンパス乱択アルゴリズムが
+ 次数2dの頂点はクラスタ係数0
+ クラスタ係数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
-- これで、各頂点について(ε,δ)近似
* 実験
- 比較方法に色々使っていて面白い
++ 平均相対誤差
++ Pearson相関係数
++ Spearman 順位相関係数
- どうも真の値と近似値にはかなりの開きがあるように見える(´・ω・`)
- 大体数百並列している感じ
- ちょっと結果もはしょっている
- 主張:
- 次数分布が歪んでいると推定が良い
- 近似が辺でもまぁ、相関はある
* まとめ
- アルゴリズムはちょっとおもしろいかも
- ただ、CheckTwoPathsは各頂点について1回しかwedgeを確かめないので勿体無い気がした
- 相関はちょー適当な推定でも出る気がするのであんまり参考にならなさそう
-- 次数でとかね？
&tags()
&update()
* On the Streaming Complexity of Computing Local Clustering Coefficients
- Konstantin Kutzkov, Rasmus Pagh
- WSDM 2013
* 概要
- ワンパスでlocal clustering coefficientを求めたい
-- ローカルなので、頂点ごと
-- 辺リストが任意の順でもらえる
+ 全く三角形が無い or 1/2以上のCCを持つ次数2d以上の頂点がある、かをある程度の確率でワンパスで判定するためにはΩ(m/d)ビット必要
+ ↑の限界にマッチした乱択アルゴリズムを考案
* Lower bound
- Theorem 1
- ワンパス乱択アルゴリズムが
+ 次数2dの頂点はクラスタ係数0
+ クラスタ係数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
-- これで、各頂点について(ε,δ)近似
* 実験
- 比較方法に色々使っていて面白い
++ 平均相対誤差
++ Pearson相関係数
++ Spearman 順位相関係数
- どうも真の値と近似値にはかなりの開きがあるように見える(´・ω・`)
- 大体数百並列している感じ
- ちょっと結果もはしょっている
- 主張:
- 次数分布が歪んでいると推定が良い
- 近似が辺でもまぁ、相関はある
* まとめ
- アルゴリズムはちょっとおもしろいかも
- ただ、CheckTwoPathsは各頂点について1回しかwedgeを確かめないので勿体無い気がした
- 相関はちょー適当な推定でも出る気がするのであんまり参考にならなさそう
-- 次数でとかね？
&tags()
&update()
