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-β)
  • 分散が固有値で分かる,で,αの凸関数,簡単に最小化できる

実験

  • 以下を計算する
    • 次数分布
      • 特定の次数の頂点に遭遇したらカウントアップ
    • クラスタ係数
  • 結構サンプル数必要だよなあ

まとめ

  • むしろ今までこういうことやってなかったんスカ….

INFOCOM グラフサンプリング ランダムウォーク

2014/12/30 21:51

最終更新:2014年12月30日 21:52