Estimating Sizes of Social Networks via Biased Sampling - todo314 @ ウィキ

Estimating Sizes of Social Networks via Biased Sampling

• Liran Katzir, Edo Liberty, Oren Somekh
  • Yahoo! Labs, Israel
• WWW 2011

概要

• ネットワークのサイズ=頂点数を見積もりたい
• どういうシチュエーション？
  • FacebookとかTwitterとか…隣接リストは辿れるけどexplicitに|V|が得られない
• ランダムウォークベースのアルゴリズム
  • 一様サンプリングでなくて次数でバイアスがかかっているのがポイント
• 一様よりも高性能であることを実験で示した

サンプリング

• 誕生日パラドックスに基づいた手法
  • rノードを一様サンプリングすると、期待値C~r^n/2n回のcollisionが発生する
  • n≒r^2/2Cで見積もる
  • O(√n)サンプルで良い
• どうやって一様サンプリングするの？
• ランダムウォーク！
  • ランダムウォーク中、今頂点vにいる
  • 確率1/d_vでその頂点を保存、そうでなければ破棄
  • 定常状態から選ばれる確率はd_vに比例するので、破棄されなかった頂点は一様な確率で選ばれている
  • 問題：全体でn/Dの確率で保存するので、Ω(√n)個の一様サンプルを得るにはΩ(D/√n)回のランダムウォークが必要
• Metropolis-Hastings random walk
  • vi→vjの遷移は確率1/max(di, dj)

Collision countingベース

• r回ランダムウォークした
• C: collisionの発生回数
• E[Ψ_1]: 各頂点の次数の和
• E[Ψ_-1]: 各頂点の次数の逆数和
• $$ n \approx \frac{E[\Psi_1]E[\Psi_{-1}]}{2E[C]} $$
• rのboundが複雑だけど抑えられている
• もしregularならO(√n)になる

Zipfian分布に従う場合

• ちょっと違うけどsocial networkを想定
• $$ O(n^{1/4}\log n) $$に減る
• 隠れ定数を考えなければn=10^9とかでは5倍の差が出る
• この5倍は実験でもそんな感じの結果が出ているっぽい

サブグラフのサイズ

• よくわからなかった

Non-unique element counting estimator

• こっちのほうが精度良いらしい
• non-unique: 今までそれが1回以上出現している
• 1,2,3,1,1,2だったら、最後の3つは全部non-unique
• collisionはペアなので、同じ要素の出現数の自乗だけど、こっちは同じ要素の出現数に比例するだけなので、良いらしい
• 方程式を解いて求める

実験

• 1Mくらいの大きさでやる
• 一様サンプリングは提案手法（次数でバイアスかかっている）よりも収束が遅い
• Facebookでもやってたけどよーわからん

まとめ

• Estimating Clustering Coefficients and Size of Social Networks via Random Walkの前進だなあ
  • Liran Katzirがどちらにもいるので
• 最初一様サンプリングとか無理じゃね？とか思ったけど、ランダムウォークすごいなあ…

WWW random walk sampling

2013-12-16 14:31:41 (Mon)