iwiwi 備忘録

学んだことを殴り書きます。自分向けのメモです。

First Passage Time for Random Walks in Heterogeneous Networks (PRL'12)

  • 概要
  • 用語&既存の結果
    • スペクトル次元
    • RTO (return to the origin) probability R(t)
      • t ステップ後に元の頂点に戻る確率
      • R(t) 〜 t^{-d_s / 2}
      • R_m(t):頂点 m に関するもの
      • 同グループ PRE'12:R_m(t) は 3 フェーズに分かれるとか
    • FPT F_{mi}(t) := m から i
    • GFPT F_m(t) := 定常分布から m
    • T_m:GFPT の平均
  • 結果
    • d_s の値によって T_m は 3 パターンに分かれる
    • d_s < 2 だと,頂点への到達しやすさが次数によらない(!?)
    • それ意外では,ハブが最も到達しやすい
    • d_s > d_c (=2(γ-1)/(γ-2)) のとき,線形より早くハブに到達できる