A General Framework of Hybrid Graph Sampling for Complex Network Analysis
-
Xin Xu, Chul-Ho Lee, Do Young Eun
-
INFOCOM 2014
概要
-
グラフをサンプリングしたい
-
ランダムウォークとかランダムジャンプとかある
-
↑を統合したのを考えて解析
-
分散(小さいと良)がランダムジャンプ確率に対して凸
既存手法
-
ランダムウォーク
-
Simple Random Walk (SRW) with Re-weighting
-
Metropolis-Hastings Random Walk (MHRW)
-
収束に時間が掛かる
-
一様頂点サンプリング
-
‘Random Jump’ based on Rejection Sampling
-
普通ID空間は疎なので辛い
-
上の組み合わせ
ランダムウォーク
-
Markov Chainになる
-
極限は定常分布に収束(条件下)
-
分散が評価基準
-
Metropolis-Hastings Random Walk
提案枠組
-
Ω: ID全体の集合
-
N: 現在あるID集合
-
β=|N|/|Ω|
-
歩行者は,
-
確率1-αで,近傍に遷移
-
確率αで,IDを発行し
-
確率1-βで,その場に留まる
-
確率βで,そのIDに対応する頂点に遷移
-
P_α = (1-α)P + α(1-β)I + αβ/n 11^T
-
P_αの定常分布は一様
-
P_αの固有値分布が知りたい
-
Pの固有値がλiだとすれば,P_αの固有値は(1-α)λi+α(1-β)
-
分散が固有値で分かる,で,αの凸関数,簡単に最小化できる
実験
まとめ
INFOCOM グラフサンプリング ランダムウォーク
2014/12/30 21:51
最終更新:2014年12月30日 21:52