First Passage Time for Random Walks in Heterogeneous Networks - todo314 @ ウィキ

First Passage Time for Random Walks in Heterogeneous Networks

• S. Hwang, D.-S. Lee, B. Kahng
• PRL 2012

概要

• スケールフリーネットワーク上のランダムウォーク
• 次数kの頂点への到達のしやすさ：3パターン（ベキ指数γ、スペクトル次元で分ける）

色々

スペクトル次元

• ラプラシアン行列の固有値の分布のベキのところ
• 何か固有値ソートして並べたのをフィッティングしたとするらしい

RTO(Return to the origin)

• R(t): tステップ後に元の頂点に戻る確率
• スペクトル次元が関係
• ホントは頂点毎に変わるよ！
• 次数で式が3パターンになるらしい
• シミュレーションするとよさそう

FPT(first passage time)

• 次数kの頂点への到達のしやすさ
• 母関数とか使っちゃう