「A General Framework of Hybrid Graph Sampling for Complex Network Analysis」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* A General Framework of Hybrid Graph Sampling for Complex Network Analysis
- Xin Xu, Chul-Ho Lee, Do Young Eun
- INFOCOM 2014
* 概要
- グラフをサンプリングしたい
-- どっちかっていうとΣf(v)を近似したい
- ランダムウォークとかランダムジャンプとかある
-- ランダムジャンプはたまに失敗する
- ↑を統合したのを考えて解析
- 分散（小さいと良）がランダムジャンプ確率に対して凸
* 既存手法
- ランダムウォーク
-- 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はMHRWとする
- P_αの定常分布は一様
- P_αの固有値分布が知りたい
- Pの固有値がλiだとすれば，P_αの固有値は(1-α)λi+α(1-β)
- 分散が固有値で分かる，で，αの凸関数，簡単に最小化できる
* 実験
- 以下を計算する
-- 次数分布
--- 特定の次数の頂点に遭遇したらカウントアップ
-- クラスタ係数
- 結構サンプル数必要だよなあ
* まとめ
- むしろ今までこういうことやってなかったんスカ…．
&tags()
2014/12/30 21:51
* A General Framework of Hybrid Graph Sampling for Complex Network Analysis
- Xin Xu, Chul-Ho Lee, Do Young Eun
- INFOCOM 2014
* 概要
- グラフをサンプリングしたい
-- どっちかっていうとΣf(v)を近似したい
- ランダムウォークとかランダムジャンプとかある
-- ランダムジャンプはたまに失敗する
- ↑を統合したのを考えて解析
- 分散（小さいと良）がランダムジャンプ確率に対して凸
* 既存手法
- ランダムウォーク
-- 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はMHRWとする
- P_αの定常分布は一様
- P_αの固有値分布が知りたい
- Pの固有値がλiだとすれば，P_αの固有値は(1-α)λi+α(1-β)
- 分散が固有値で分かる，で，αの凸関数，簡単に最小化できる
* 実験
- 以下を計算する
-- 次数分布
--- 特定の次数の頂点に遭遇したらカウントアップ
-- クラスタ係数
- 結構サンプル数必要だよなあ
* まとめ
- むしろ今までこういうことやってなかったんスカ…．
&tags()
2014/12/30 21:51
