Sampling Node Pairs Over Large Graphs

Sampling Node Pairs Over Large Graphs

  • Pinghui Wang, Junzhou Zhao, John C.S. Lui, Don Towsley, Xiaohong Guan
  • In ICDE 2013

概要

  • ノードのペアに関する性質
    • 平均距離とか
  • サンプリングで求めるが
  • 一様っぽいサンプリングは一様じゃない
  • xを決める、u,vをxの近傍から決める
  • [u,v]が選ばれる確率は$$ \sum_{u-x-v}{\deg(x) \choose 2}^{-1} $$に比例
  • biasがかかる
  • 提案手法
    • weighted vertex sampling
    • neighborhood random walk

問題

  • $$ S=\{ [u,v] \mid u \neq v \} $$
    • |V|(|V|-1)
  • one-hop $$ S^{(1)}=\{ [u,v] \mid (u,v) \in E \} $$
    • 2|E|
  • two-hop $$ S^{(2)}=\{ [u,v] \mid u \neq v, \exists x: u \rightarrow x \leftarrow v \} $$
    • >|V|
  • $$ S^{(2+)}=S^{(2)} \cup S^{(1)} $$
  • $$ S^{(1-)}=S^{(1)} \setminus S^{2} $$
    • 連結だけど共通近傍なしなペア
  • F(u,v): ペアの性質(距離、共通近傍の数、等)
  • F(u,v)の値の範囲: {a1,…,aK}
  • $$ \omega^{(i)} = (\omega_1^{(i)}, \cdots, \omega_K^{(i)}) $$
    • $$ \omega_k^{(i)} $$: S^(i)でのakの割合
  • これで次が成り立つ
    • $$ \omega^{(2+)} = \frac{\alpha\beta \omega_k^{(1-)} + \omega_k^{2}}{\alpha\beta +1} $$
  • このωベクトルを求めるのが問題

提案手法

Uniform vertex sampling ベース

independent weighted vertex sampling (IWVS)

  • 何か定常分布πを決める
  • vをπ_vで選ぶ
    • O(log|V|)

Metropolis-Hastings based weighted vertex sampling (MHWVS)

  • π_vがめんどいとき
  • Metropolis-Hastings
    • 適当にvを選んだ後ランダムウォークっぽい事をする(多分
    • 遷移確率は色々変えている

Sからのサンプリング

  • 2頂点をそれぞれ適当にとってくるだけ

S^(1)からのサンプリング

  • π_x=d_x/2|E|
  • ↑でuをサンプリング、vはuの近傍から一様

S^(2)からのサンプリング

  • π_x=d_x*(d_x-1)/M
  • ↑でxを選んだ後、u,vを近傍から

Random walk ベース

  • 状況: グラフ全体が分からん or ランダムIDを生成するのが高コスト
  • $$ V^{(2)} = \{ [u,v] \] $$
  • $$ E^{(2)} = \{ ([u,v], [x,y]) \mid (u,x),(v,y) \in E \} $$
  • こんなグラフを作って
  • $$ \pi_{[u,v]} = \frac{d_u d_v}{4|E|^2} $$
  • S^(1)、S^(2)もそんな感じ

実験

データセット

  • Wiki-vote, P2P-Gnutella, soc-Epinions, soc-Slashdot

評価基準

  • normalized mean square error
    • 小さい方がいい
    • 1なら許容範囲内

距離分布

  • Kは直径になる(当たり前
  • ある程度サンプリングするといい感じ

共通近傍分布

  • S^(1)とS^(2)

類似度分布

  • よく分からん

まとめ

  • 大きな問題なのかあ
    • 難しさをわかっていないだけ感あるかもね
  • 状況をちゃんと(自分が)考えないといけないのかも
    • 例えば、一個頂点をランダムサンプリングってのが何回もやると高コスト、とか
    • 近傍なら簡単にとってこれるならランダムウォークとか…
  • 解析は完全にすっ飛ばしてしまった
最終更新:2013年10月28日 17:51