数理解析研究所講究録
第 1849 巻 2013 年 100-104100

動的グラフ上のランダムウォークの到達時間と全訪問時間
Hitting time and cover time on dynamic graphs
木場孝輔

山内由紀子

来嶋秀治

山下雅史

Kosuke Koba

Yukiko Yamauchi

Shuji Kijima

Masafumi Yamashita

九州大学
Kyushu University1の各辺が Markov 連鎖として変化するモデルも扱う．

はじめにそのグラフ上の単純ランダムウオークについて，グラグラフ上のランダムウォークとは，トークンがグ フをパスに限定した場合の到達時間の上界を求める．
ラフの頂点をランダムに遷移していく確率モデルである．グラフ上のランダムウォークは，インターネッ
準備
トクローラーやネットワークの探索などに応用され 2ている．静的なネットワーク上でのランダムウォ
2.1 ランダムウォーク
クに関しては，多くの従来研究が存在する．しかし，ー

インターネットなどの現実のネットワークは時不変ではなく，故障やエラーなどによって時間と共に変化する動的なネットワークであることが多い．そこ
で，本発表ではこのような動的ネットワークを対象

グラフ $G=(V,E)$ について，ある頂点 $u\in V$に隣接する頂点の集合を $N(u)$ で表し， の次数を$u$$\deg(u)$と書く．グラフ$G$上のランダムウォークとは，グラフ上の頂点をトークンが遷移確率行列 $P=$$(P(u,v))(u,v\in V)$ に従って確率的に遷移していくとする．

動的グラフ上でのランダムウォークについての先行 モデルである．
研究としては，辺集合のみが変化するグラフ [1,2,3]すべての隣接頂点に対して等確率で遷移するランが[2]や，頂点が追加されていくグラフを扱ったもめダムウォークを単純ランダムウォークという．
任意の正のベクトル $\mu=(\mu_{u})(u\in V_{)}\mu_{u}>0)$ がある．

本発表ではまず，辺集合が変化するグラフとして， 与えられたとき，メトロポリスウォークは以下の遷
各時刻においてグラフの各辺が独立に確率 で消え 移確率行列によって定義される．
$q$$R_{\mu}$るとしたモデルを考える．このモデルに対し，定常分布を任意に設定できるという特徴を持つメトロポ
リスウォーク [4] を元に，動的グラフ上でのランダム$R_{\mu}(u,v)=[Matrix]$ウォークの戦略を提案する．そして，その到達時間と全訪問時間，定常分布を解析する．さらに，ベルヌーイグラフ上で，定常分布を任意に設定できるランダムウォークの戦略を提案，解析する．

次に，より一般的なグラフモデルとして，グラフ

2.2

定常分布

$\forall u\in V,\pi(u)=\Sigma_{v\in V}\pi(v)P(v,u)$を満たす確率分布 $\pi=(\pi(u))(u\in V)$ を定常分布と呼ぶ．メトロ101
ポリスウォークの定常分布は$\pi\propto\mu$である [4].

3.2

ベルヌーイグラフ上のメトロポリス
ウォーク

2.3

到達時間と全訪問時間任意の正のベクトル $\mu=(\mu_{u})(u\in V, \mu_{u}>0)$ がグラフ $G=(V, E)$ 上の遷移確率行列 $P$ に従うランダムウォークがあるとする．このとき頂点 $u\in V$ にあるトークンが，頂点 $v\in V$ に到達するまでの遷移数の期待値を， から への到達時間 (Hitting time)$u$と定義し与えられているとする．各時刻ンが頂点 $u\in V$$t$において，トークにいるとき，以下のように動く．

1. もし， 上で隣接頂点が 1 つも無いならば現在$G_{t}$$v$の頂点にとどまる．

で記述する．その最大値を $H^{P}:=$$H_{u,v}^{P}$と定義する．2. そうでなければ， での隣接頂点$G_{t}$$\max_{u},{}_{v}H_{u,v}^{P}$

等確率に 1 つ選び

また，頂点 $u\in V$ にあるトークンが，グラフ上のすべての頂点を訪れるまでの遷移数の期待値を，からの全訪問時間 (Cove time) と定義しで記3] 率 $\min\{1,$$u$$N_{t}(u)$から，とする．

$v$$\frac{\deg(u)\mu_{v}}{\deg(v)\mu_{u}}\}$

で$v$へ移動する．

$C_{u}^{P}$

$-r$

命題

$\grave{J}^{\prime\backslash }1T6\cdot\epsilon$の$\ovalbox{\tt\small REJECT}$

大を $C^{P}:= \max_{u}C_{u}^{P}$ と定義する．

ベルヌーイク -7 フ上のメトロボリスウォー$\grave{}\grave{}\check{}$$arrow Qp\not\in 3\cdot 2$$\llcorner$

クの遷移確率行列$\mu$

3

ベルヌーイグラフ上のランダム$P_{\mu}$は，変化のなレゾラフを与えたときのメトロポリ行列$R_{\mu}$$\lambda$$G$

上でウォークの遷移確率を用いて，以下のように表せる．

ウ $*$ -ク
ベルヌーイグラフ$P_{\mu}(u,v)=\{\begin{array}{ll}(1-q^{\deg(u)})R_{\mu}(u,v) v\in N(u) ,q^{\deg(u)}+(1-q^{\deg(u)})R_{\mu}(u,u) u=v,\end{array}$$\# 3\cdot 1$

辺集合が変化するグラフとして，以下のモデルを

otherwise$0$

モデル 3.1 与えられるグラフ $G=(VE)$ は単純無向連結とする．時刻 $t\in N$ におけるグラフ $G_{t}=3\cdot 3$$V_{t}=V,$(Vt, $E$のは，$E_{t}$

は $E$ の各辺を独立に確率$1-q$ で選んでできる辺の集合とし，以下を満たす．

本節では，ベルヌーイグラフ上のメトロポリスウ
ォークの到達時間と全訪問時間について，静的なグラフ上のランダムウォークの到達時間，全訪問時間$Pr(E_{t}\ni e)=1-q$ .

$\forall t\in N,e\in E$

到達時間と全訪問時間の解析との比較を行う．
$G$

このモデルは，各時刻において，元となるグラフの各辺が独立に確率 で消え，確率 $1-q$ で残っ 定理 3.3 ベルヌーイグラフ上のメトロポリスウォー$q$ているというものである．クの到達時間$n=|V|,$ $m=|E|$
以下で用いる記号を定義する．とする．元となるグラフ における の隣接頂点の集合を $N(u)$ で表し， に接続する辺の数を $\deg(u)$$G$$u$$u$とする．時刻のグラフにおけるの隣接頂点の集合を $N_{t}(u)$ とし， に接続する辺の数を $\deg_{t}(u)$$t$$G_{t}$$N_{t}(u)\subseteq N(u)$ が成り立 $0$ .とする．明らかに，$\delta$, 最大次数を$C_{u}^{P_{\mu}}$は以下を満たす．
$H_{wv}^{R_{\mu}}$$H_{u,v}^{R_{\mu}}$$\overline{1-q\triangle}\overline{-q\delta}\leq H_{u,v}^{P_{\mu}}\leq_{1}’$$C_{u}^{R_{\mu}}$‘$C_{u}^{R_{\mu}}$$\overline{1-q\Delta}\leq c_{u}^{P_{\mu}}\leq_{\overline{1-q\delta}}.$

$u$

$u$

ラフ $G$ の最小次数をと全訪問時間$H_{u,v}^{P_{\mu}}$$\Delta$とする．

グ

ここで$H_{u,v}^{R_{\mu}}$と$C_{u}^{R_{\mu}}$

は，変化のないグラフ$G$

上で$\mu$を与えたときのメトロポリスウォークの到達時間と全訪問時間である．

$\cdot$102
グラフ $G$ の次数が大きくなるほど，ベルヌーイグ

ラフ上のメトロポリスウォークの到達時間，全訪問$=$$H_{u,v}^{P_{\mu}}$

時間は，変化のないグラフ $G$ 上でのメ トロポリス$\sum_{t=1}^{\infty}\sum_{w\in W_{u,v}^{R_{\mu}},|w|=t+1}$

ウォークの到達時間，全訪問時間に近づく．
$\{(\prod_{i=1}^{t}R_{\mu}(w_{i}, w_{i+1}))\sum_{j=1}^{t}\frac{1}{1-q^{\deg(w_{j})}}\},$

補題 3.4 ある遷移確率行列 $P=(P(u, v))(u, v\in V)$が与えられるとする．このとき，グラフ上の各頂点$u$$0\leq q_{u}<1$ である，任意のに対し，れ，遷移確率行列$P’$$q_{u}$が与えら$=$$C_{u}^{P_{\mu}}$が以下のように書けるとする．
$)$$\sum_{t=1}^{\infty}\sum_{w\in W_{u}^{R_{\mu}},|w|=t+1}$,$\{(\prod_{i=1}^{t}R_{\mu}(w_{i}, w_{i+1}))\sum_{j=1}^{t}\frac{1}{1q^{\deg(w_{j})}}\}.$$P’(u, v)=\{\begin{array}{ll}(1-q_{u})P(u, v) v\in N(u), u\neq vq_{u}+(1-q_{u})P(u, u) u=v,0 otherwise.\end{array}$$\delta-$

ここで，グラフ上の頂点の最小次数 , 最大次数

このとき，到達時間と全訪問時間は$\Delta$$G$ 上のメ トロポリスウォークの到達時間，全と，訪問時間を用いると，定理 3.3 が得られる$H_{u,v}^{P’}$$=$口$\sum_{t=1}^{\infty}\sum_{w\in W_{u,v}^{P},|w|=t+1}$

3.4

ベルヌーイグラフ上のメトロポリス
ウォークの定常分布$\{(\prod_{i=1}^{t}P(w_{i}|, w_{i+1})) \sum_{j=1,)}^{t}\frac{1}{1-q_{w_{j}}}\},$

2.2 節で述べたとおり，静的なグラフ上では，メトロポリスウォークにより所望の定常分布が実現でき$C_{u}^{P’}$$=$

る．しかし動的なグラフ上では，定常分布が所望の$\sum_{t=1}^{\infty}\sum_{w\in W_{u}^{P},|w|=t+1}$

分布に一致しないことを示す．
$\{(\prod_{i=1}^{t}P(w_{i}, w_{1+1}))\sum_{j=1}^{t}\frac{1}{1-q_{w_{j}}}\},$

定理 3.5 ベルヌーイグラフ上のメトロポリスウォ

クの定常分布

$\pi_{\mu}=(\pi_{\mu}(\‘{u}))$ー$(u\in V)$ は以下のようになる．となる．ただし$W_{u,v}^{P}$は， 上で $P$ に従うランダム$G$

ウォークを行ったときにとりうる体の集合であり，$W_{u}^{P}$

$u$

から$v$

$\pi_{\mu}(u)\propto\frac{\mu_{u}}{1-q^{\deg(u)}}.$への道全

は， から全訪問するのにと$u$

証明$\forall u\in V,$$\pi_{\mu}(u)=k\cdot\frac{\mu_{u}}{1-q^{\deg(u)}}$とする． は正規化定数であり，りうる道全体の集合である．

$k=1/ \sum_{w\in V}\frac{\mu_{w}}{1-q^{d\circ g(w)}}$

任意の 2 頂点 $u,$$|w|$
道 $w\in$ Wu ,。に対し，で道の長さを表す．例えば

$v$

$\in$

$V$$k$である．

$\deg(u)\mu_{v}$に対して，$<$$P$$w$$\deg(v)\mu_{u}$のとき，$uarrow v_{1}arrow v_{2}arrow v_{2}arrow v$ という道を表すとき，が，$w=(w_{1}, w_{2}, w_{3}, w_{4}, w_{5})=(u, v_{1}, v_{2}, v_{2}, v)$

であり，$|w|=5$ である．同様に $w’\in W_{u}^{P}$ についても $|w’|$ は$\pi_{\mu}(u)P_{\mu}(u, v)$$=k \cdot\frac{\mu_{u}}{1q^{\deg(u)}}\frac{1-q^{\deg(u)}}{\deg(u)}\min\{1,$$\frac{\deg(u)\mu_{v}}{\deg(v)\mu_{u}}\}$

道の長さを表す．
$=k \cdot\frac{-\mu_{v}}{\deg(v)}$証明(定理 3.3) 補題 3.4 より，ベルヌーイグラフ

上のメトロポリスウォークの到達時間と全訪問時間は$=k \cdot\frac{\mu_{v}}{1-q^{\deg(v)}}\frac{1-q^{\deg(v)}}{\deg(v)}\min\{1,$ $\frac{\deg(v)\mu_{u}}{\deg(u)\mu_{v}}\}$$=\pi_{\mu}(v)P_{\mu}(v, u)$.

103$\deg(u)\mu_{v}\geq\deg(v)\mu_{u}$$=\pi_{\mu}(v)P(v, u)$

モデル 4.1 与えられるグラフ $G=(V, E)$ は単純のときも同様に，$\pi_{\mu}(u)P(u, v)$となる．よって任意の 2 頂点に対して，$\pi_{\mu}(u)P(u, v)=\pi_{\mu}(v)P(v, u)$

したがって？ $\pi_{\mu}=(k\cdot\frac{\mu_{u}}{1-q^{\deg(u)}})(u\in V)$$u,$ $v\in

無向連結とする．確率V$$p,$を満たす．られているとする．時刻
$|$

ま，ベノレ

$(V_{t}, E_{t}),$

ヌーイグラフ上でのメトロポリスウォークの定常分布である$e\in E$

$V_{t}=V$$q(0<p, q<1)$ が与え$t$におけるグラフを $G_{t}=$とする．各時刻 こおいて，各辺$t$$|$が，以下のような遷移確率に従って変化する．

口定理 3.5 より，3.2 節のメトロポリスウォークでは，定常分布が与えた$\mu$に比例しない．次の節では，$\mu$に比例する定常分布を持つランダムウォークを示す．

3.5

ベルヌーイグラフ上で，所望の定常分布を持つメトロポリスウォーク

このモデルは $1-p=$$q$のとき，モデル 3.1 と等しい．特に， としてパスグラフが与えられたと$G$

定理 3.5 より，3.2 節のメトロポリスウォークに$\{n-$1 $q^{\deg(u)})$ を与えることで， に比例す き $(V=\{1,2, \ldots, n\},$ $E=\{\{1,2\},$ $\{2,3\},$$n\}\})$ ,パスと呼ぶ．
Markovian
る定常分布を持っランダムウォークを得ることができる．このときの遷移確率行列は，命題 3.2 から得られる．また，このランダムウォークの到達時 4.2 Edge-Markovian グラフ上の単純ラ$\mu’=\mu_{u}$$($$\ldots,$–$\mu$$1,$$P_{\mu’}$間$H^{P_{\mu’}}$

,

全訪問時間

$C^{P_{\mu’}}$}は，定理 3.3 によって抑えられる．ここで，$H^{R_{\mu’}}=O(f’\cdot n^{2}),$$O(f’\cdot n^{2}\log n),$$f_{\overline{\tau}}’ \frac{\max_{u\in V}\mu’}{\min_{u\in V}\mu_{u}’}$である [4].

ンダムウォーク$C^{R_{\mu’}}=$

各時刻

よって，において，トークンが頂点 $u\in V$ にいる

とき以下のように動く．

以下のような上界が得られる．
$H^{P_{\mu’}}=O( \frac{f’}{1-q^{\delta}}\cdot n^{2})$$t$1. もし，研上で隣接頂点が 1 つも無いならば現在,の頂点にとどまる．
$C^{P_{\mu’}}=O( \frac{f’}{1q^{\delta}}\cdot n^{2}\log n)$

さらに，$\mu$.

2. そうでなければ， での隣接頂点瓦 $(u)$ から等確率に 1 つ選び，そこへ移動する．
$G_{t}$が一様のとき- は，以下のようになる．

$H^{P_{\mu’}}=O( \frac{1-q^{\Delta}}{(1-q^{\delta})^{2}}n^{2})$,4.3

Markovian パス上の単純ランダムウ
ォークの到達時間$c^{P_{\mu’}}=O( \frac{1-q^{\Delta}}{(1-q^{\delta})^{2}}n^{2}\log n)$.

グラフを Markovian パスに限定したときの，単純ンダムウォークの到達時間の上界を示す．

$\ovalbox{\tt\small REJECT}$

4

Edge-Markovian グラフ上のランダムウォーク$P$$E$)

理 4. $21-p\geq q$ である Markovian パス上の，単ffi ランダムウォークの到達時間$j’$$\mathcal{T}.$4.1

Edge-Markovian グラフ

モデル 3.1 の拡張として，以下のモデルを扱う．

$H^{P}$

は，以下を満た$1-p\geq q$ である Markovian パス上の単純ラン

104[3] K. Koba, S. Kijima, M. Yamashita, Randomは以下を満たす．walks on dynamic graphs, Proc. WAAC 2011,

ダムウォークにおいて，端点からもう一方の端点までの到達時間$H_{1,n}$28-35.
$b(n-1)$$(a- \frac{b}{p+q-1})(1-(4\Delta)^{n-1}),$$[4]$$H_{1,n}^{P}\leq_{\overline{pq-1}}++\overline{1-(\frac{2-}{p}L^{-}\Delta)}$$a=1+ \frac{\max\{1-\mu_{\{1,2\}},1-q\}}{q}$,$b=1+ \frac{p(1-q)}{1(1q)^{2}}.$

ここで$\mu_{\{1,2\}}$は，初期グ-ラフ$-G_{1}$において辺 {1, 2}が存在する確率である．

5

おわりにグラフ $G$ 上の各辺が各ステップ毎に独立に確率$p$で消えるモデル上でのメトロポリスウォークについて，その到達時間と全訪問時間，定常分布を解析した．定常分布を任意に設定できるランダムウオークを提案し，その到達時間と全訪問時間の上界を求めた．さらに，グラフ の各辺が Markov 連鎖として変化するモデル上の単純ランダムウォークについて，グラフをパスに限定した場合の到達時間の上界を求めた．しかし，その上界は頂点数について指数の上界であるため，頂点数の多項式で抑えられないか考える必要がある．また，パス以外のグラフについて$G$解析することも，今後の課題である．

参考文献[1] C. Avin, M. Koucky, Z. Lotker, How to explore
a fast-changing world (Cover time of a simple
random walk on evolving graphs), LNCS, 5125$(2m8),$ $121-132.$[2] C. Cooper, Random walks, Interacting particles, dynamic networks: Randomness can be
helpful, LNCS, 6796 (2011), 1-14.

Y. Nonaka, H. Ono, K. Sadakane, M.
Yamshita, The hitting and cover times ofMetropolis walks, Theoretical Computer Science Volume 411 Issue 16-18, 2010, $188k1894$