Aritalab:Lecture/NetworkBiology/Random Walk

Wiki Top

Up one level

レポートの書き方

Arita Laboratory

グラフ上のランダムウォーク

グラフ G(V,E) の各頂点 u から出る辺を等確率 $1/d(u)$ で選んで動くグラフ上のランダムウォークを考えよう。 非周期性を仮定したいので、以下では二部グラフでない連結なものだけを考慮する。

定理： 頂点 u から v に到達するステップ数の期待値を $h_{u,v}$ と記述すると $\textstyle h_{u,u} = \frac{2|E|}{d(u)}$ が成立。

証明

まずランダムウォークの定常分布 $\bar \pi$ が $\textstyle \frac{d(v)}{2|E|}$ であることを示そう。 定常分布における各頂点上の確率 $\pi_v$ の総和をとると $\textstyle \sum_{v \in V} \pi_v = \sum_{v \in V} \frac{d(v)}{2 |E|} = 1$。

また 　から、 $\textstyle \frac{d(v)}{2|E|}$　は定常分布の条件を満たす。

頂点への再帰時間の期待値は $\textstyle \frac{1}{\pi_u}$ であることを使うと証明は終わり。

補題

隣り合う頂点間のステップ数の期待値の上限は $2 |E|$ で抑えられる。なぜなら

$\textstyle 2|E| = h_{u,u} \cdot d(u) = \sum_{v \in adj(u)} (1+ h_{v,u}) > h_{v,u}$

さらにグラフ全体を訪れるのに必要な期待値の上限は $4 |V| \cdot |E|$ で抑えられる。与えられたグラフのスパニング木を作ると、その上を全点辿ったときの辺数が $(2|V|-2)$ のため

$\textstyle \sum_1^{2|V|-2} h_{u,v} = (2|V|-2) \cdot 2|E| < 4|V|\cdot |E|$

このように、ある頂点から出発したランダムウォークが全ての頂点を訪れるまでの期待ステップ数をグラフの被覆時間 (cover time) と呼ぶ。