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 \} $$
-
one-hop $$ S^{(1)}=\{ [u,v] \mid (u,v) \in E \} $$
-
two-hop $$ S^{(2)}=\{ [u,v] \mid u \neq v, \exists x: u \rightarrow x \leftarrow 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)
Metropolis-Hastings based weighted vertex sampling (MHWVS)
-
π_vがめんどいとき
-
Metropolis-Hastings
-
適当にvを選んだ後ランダムウォークっぽい事をする(多分
-
遷移確率は色々変えている
Sからのサンプリング
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
距離分布
-
Kは直径になる(当たり前
-
ある程度サンプリングするといい感じ
共通近傍分布
類似度分布
まとめ
-
大きな問題なのかあ
-
状況をちゃんと(自分が)考えないといけないのかも
-
例えば、一個頂点をランダムサンプリングってのが何回もやると高コスト、とか
-
近傍なら簡単にとってこれるならランダムウォークとか…
-
解析は完全にすっ飛ばしてしまった
最終更新:2013年10月28日 17:51