Aritalab:Lecture/NetworkBiology/Random Walk
From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
m |
|||
Line 5: | Line 5: | ||
非周期性を仮定したいので、以下では二部グラフでない連結なものだけを考慮する。 | 非周期性を仮定したいので、以下では二部グラフでない連結なものだけを考慮する。 | ||
− | + | '''[定理]''' 頂点 ''u'' から ''v'' に到達するステップ数の期待値を <math>h_{u,v}</math> と記述すると <math>\textstyle h_{u,u} = \frac{2|E|}{d(u)}</math> が成立。 | |
;証明 | ;証明 | ||
Line 29: | Line 29: | ||
= \sum_{v \in adj(u)} (1+ h_{v,u}) > h_{v,u}</math> | = \sum_{v \in adj(u)} (1+ h_{v,u}) > h_{v,u}</math> | ||
− | さらにグラフ全体を訪れるのに必要な期待値の上限は <math>4 |V| | + | さらにグラフ全体を訪れるのに必要な期待値の上限は <math>4 |V| |E|</math> で抑えられる。与えられたグラフのスパニング木を作ると、その上を全点辿ったときの辺数が <math>(2|V|-2)</math> のため |
<math>\textstyle | <math>\textstyle |
Revision as of 06:05, 8 July 2010
Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
グラフ上のランダムウォーク
グラフ G(V,E) の各頂点 u から出る辺を等確率 で選んで動くグラフ上のランダムウォークを考えよう。 非周期性を仮定したいので、以下では二部グラフでない連結なものだけを考慮する。
[定理] 頂点 u から v に到達するステップ数の期待値を と記述すると が成立。
- 証明
まずランダムウォークの定常分布 が であることを示そう。 定常分布における各頂点上の確率 の総和をとると 。
また Failed to parse (lexing error): \textstyle \bar \pi {\mathbf P} = \sum_{u \in adj(v)} \pi_u \frac{1}{d(u)} = \sum_{u \in adj(v)} \frac{1}{2 |E|} = \frac{d(v)}{2|E|} = \bar \pi から、 は定常分布の条件を満たす。
頂点への再帰時間の期待値は であることを使うと証明は終わり。
- 補題
隣り合う頂点間のステップ数の期待値の上限は で抑えられる。なぜなら
さらにグラフ全体を訪れるのに必要な期待値の上限は で抑えられる。与えられたグラフのスパニング木を作ると、その上を全点辿ったときの辺数が のため
このように、ある頂点から出発したランダムウォークが全ての頂点を訪れるまでの期待ステップ数をグラフの被覆時間 (cover time) と呼ぶ。