Estimating Clustering Coefficients and Size of Social Networks via Random Walk - todo314 @ ウィキ

Estimating Clustering Coefficients and Size of Social Networks via Random Walk

• Stephen J. Hardiman, Liran Katzir
• In WWW 2013

メモ

• Liran KatzirはMSR Israel

概要

• ランダムウォークでクラスタ係数と頂点数を見積もる
• 全体をとってくるのが厳しい用
  • ちょっとタイムリー
• 既存手法よりかなり良い
• 近似が指数関数的によくなる（ランダムウォークの長さの
• 頂点のIDと、隣接リスト（次数）さえわかれば良い
• しかも前と後の1つずつだけ覚えていれば計算可能

問題

1. global clustering coefficient
2. average clustering coefficient
3. network size

• 参考: clustering coefficient

前提知識

Random walk

• 特定の条件が満たされていれば、random walkの定常状態は
• $$ \pi = [p_1, p_2, \cdots, p_n] $$
• $$ p_i = d_i/2|E| $$

提案手法

大事なツール

• random walk: (x1, x2, …, xr)
• $$ \phi_k = A_{x_{k-1}, x_{k+1}} $$
  • つまり、前と後が隣接しているかのindicator
• 関数f(xk) $$ E[\phi_k f(x_k)] = \sum_{i=1}^{n} \frac{1}{D}\frac{2l_i}{d_i}f(v_i) $$
• fをうまく調整してこの式をいい感じにする

average clustering coefficient

• $$ \Phi_l = \frac{1}{r-2} \sum_{2 \leq k \leq r-1}\phi_k \frac{1}{d_{x_k} -1} $$
• $$ \Psi_l = \frac{1}{r} \sum_{1 \leq k \leq r}\frac{1}{d_{x_k}} $$
• とおく、どっちも次数だけなので隣接リストがあれば計算できる
• $$ \frac{E[\Phi_l]}{E[\Psi_l]} = \frac{1}{n}\sum_{i=1}^{n}c_i = c_l $$
• 期待値的には平均クラスタ係数に一致する
  • さらに確率的な議論もしている

gloval clustering coefficient

• $$ \Phi_g = \frac{1}{r-2} \sum_{2 \leq k \leq r-1}\phi_k d_{x_k} $$
• $$ \Psi_g = \frac{1}{r} \sum_{1 \leq k \leq r} d_{x_k}-1 $$
• 上と似てる
• $$ \frac{E[\Phi_g]}{E[\Psi_g]} = c_g $$

network size

• 似たようなことをする
  • よんでない

実験

データセット

• DBLP
  • |V|=98K
• Orkut
  • |V|=3M
• Flickr
  • |V|=2M
• Live Journal
  • |V|=5M
• それぞれの係数は事前にわかっている

比較対象

• random walk combined with ego network exploration
• Metropolis-Hastings sampling with ego network

結果

• 得られた値をソートして両側5%を除いた時の最小と最大を比べる
  • ぱっと見で提案手法が良いことが分かる
• random walkの長さと係数の平均
  • 提案手法はいい感じに真値に近づく
  • 他はあんまり近づかない
  • network sizeでは圧倒的

結論

• 実験で既存手法よりよいと示した
• 解析的boundもあり

まとめ

• 問題が面白かった
• ランダムウォークできれば何でもできるなあとおもった
• 手法は期待値の方は最終的に綺麗になる
  • 確率も議論できるのでいいなあ
  • 証明で使っている手法は普通そう

WWW clustering coefficient random walk

2013-10-08 20:09:52 (Tue)