Faster Random Walks By Rewiring Online Social Networks On-The-Fly - todo314 @ ウィキ

Faster Random Walks By Rewiring Online Social Networks On-The-Fly

• Zhuojie Zhou, Nan Zhang, Zhiguo Gong, Gautam Das
• ICDE 2013

概要

• ランダムウォークでサンプリングしたい！
• Third party（全データが無いのでAPIとかでとってくる
• でも、変なところにはまりやすい（孤立したコミュニティっぽいところ
• 辺を消したり付け替えたりして、conductanceを大きくする
• ランダムウォークなので、今見てる頂点の近傍だけから操作を行う
• 定常状態に速く収束する！（mixing timeが小さい

貢献

• グラフトポロジーを変化させ、サンプリングを効率的にする、という「問題の提案」
• MTO-Samplerという「解法の提案」

予備知識

• 何が出来るのか？
  • q(v): SELECT * FROM D WHERE USER-ID = v
  • 近傍をとってくるだけ
• 指標
  • bias: 真の分布と得られた分布の距離
  • query cost: クエリ数
• Mixing Time
  • $$ \Delta(t) = \max \frac{|P_{uv}^t - \pi(v)|}{\pi(v)} $$
  • 特定のεについてΔ(t)≦εとなるtがmixing time
• Conductance
  • $$ \Phi(G) = \min \frac{(S-T\mbox{カット})}{(S\mbox{から出てる辺数})(T\mbox{から出てる辺数})} $$
  • S,TはVの分割
  • 小さいってことは、カットが小さいので、denseなグラフが数本だけで繋がっているとかそんな感じ
  • Δ(t)はΦ(G)の式で抑えられる
  • ΦがでかいほうがΔは小さいので、うれしい
• Cross-cutting edges
  • conductance最小になるカットに含まれるような辺のこと
  • 消すとまずいやつ
  • これの判定はむずかしい、NP-hard

メインアイデア

• 難しいけど、あんまりいらんやつはある程度判定できる
• Theorem 3: [Edge Removal Criteria]
  • $$ \lfloor \frac{|N(u) \cap N(v)|}{2} \rfloor + 1 > \frac{1}{2}\max \{k_u, k_v\} $$
  • ならuvはcross-cuttingでない
  • 半分以上近傍が同じだと流石にクロスにはならない、って感じ
• Theorem 4:
  • v∈V, u,w ∈ N(v) について、k_v = 3ならば、uvをuwに変更してもconductanceは下がらない
  • k次数が3だったら辺をつ付け替える

MTO-Sampler

• ↑の辺削除・付替をrandom walkしながら続ける
• 近傍だけしか見ないので、簡単
• 付け替えたら、そのまま付け替えた先へワープする
• どのくらい辺が消されるかの期待値もboundできるらしい

実験

• biasとquery costの関係について調べる
• 普通のrandom walkをするより、若干MTOのが良い
• かなり小さい相対誤差を出すためには、2倍以上違うっぽい

まとめ

• 着眼点が何か面白いなあと思った
• random walkは色々と見る
• conductanceとmixing timeとかはこういうところでちゃんと出てくるんだな
• 近傍だけで色々できると強いのかなー

ICDE random walk

2013-12-29 22:12:18 (Sun)