数理解析研究所講究録
第 1649 巻 2009 年 203-209

203

2 点連結な直並列グラフ上の高速なランダムウォーク
小野廣隆 \dag er

穂坂祐輔 **\dag er

九州大学大学院システム情報科学府

1定兼邦彦 \dag er

山下雅史 \dag er

九州大学大学院システム情報科学研究院

はじめにンダムウォークを行うような遷移確率行列を与ランダムウォークとは, 次に出現する位置が えることで, 到達時間, 全訪問時間が共に $O(n^{2})$確率的に無作為に決定されるモデルであり, ブ であるようなランダムウォークが設計でき, これラウン運動や, 証券株価の具体的モデル化に応は一般の連結なグラフにおける到達時間, 全訪問用されている. グラフ上のランダムウォークと時間の高速化の上限となっている.
は, グラフ上の頂点にある粒子を遷移確率行列
著者は 2 点連結なグラフにおいて,全ての頂点に従って隣接する頂点に遷移させていくモデル がグラフ上のいずれかの閉路}こ含まれるというである. 隣接頂点に等確率で遷移するランダムウォークを標準ランダムウォークという. グラフ$G=(V, E)$ 上のランダムウォークで, 頂点 から頂点 まで粒子が移動するのに必要な遷移数$u$$v$の期待値を $H_{G}(u, v)$ とすると $G$ の到達時間$H_{G}$を $H_{G}= \max,v\in\gamma H_{G}(u, v)$ と定義する. また頂点を出発した頂点が他の全ての頂点を訪れるまでに要する遷移数の期待値を,CG(u) とする$u$と, $G$ の全訪問時間を $C_{G}= \max_{u\in}vC_{G}(u)$ と定義する. ランダムウォークの高速化とは, 到達時間, 全訪問時間のより小さな遷移確率行列を与えることである.

性質を利用することで, 全訪問時間が一般の連結グラフの上限の $O(n^{2})$ より低く出来る余地があると考えており, 閉路を利用したランダムウォクの高速化手法を提案する. 提案手法により, 2ー点連結な直並列グラフにおいては $O(n\sqrt{n}\log n)$の全訪問時間を達成する遷移確率行列が存在することを発見した.

2閉路を利用した高速化

21

ハミルトン閉路

標準ランダムウォークとは各頂点で粒子が隣ハミルトン閉路とはグラフの全ての頂点を一接頂点に等確率で遷移するランダムウォークで 度ずつ通るような閉路を指す. ハミルトン閉路ある. 標準ランダムウォークの到達時間, 全訪問を持つグラフをハミルトングラフと呼ぶ. グラフ

時間については過去の研究により謙々なことが解明されている. まず Aleliusu $[2|$ らが, 頂点数, 辺数 $m$ の一般のグラフにおいて全訪問時間の上限が $2m(n-1)=O(n^{3})$ であることを示している. 次に Aldous[1] が全訪問時間に関する同様$G=(V, E)$ が以下のようなハミルトン閉路を持つとする.

$n$の上限を示し, 近年全訪問時間が最大で $4/27n^{3}$であることが知られている 3
また [3] において, 頂点数 の木グラフ上の標準ランダムウォークが到達時間, 全訪問時間が共$[$$]$$v_{1}arrow v_{2}arrow\cdotsarrow v_{n}arrow v_{1}(v_{i}\in V:i=1,2, \cdots, n)$(1)
このとき頂点 から $vj$ への遷移確率のように決める.
$v_{i}$$p_{ij}$を以下$n$$p_{ij}=\{\begin{array}{l}1 (j=i+1 \text{ま} nta i=n,j=1)0(\text{その}M)\end{array}$に $O(n^{2})$ であることが知られている. 従って任意の連結グラフにおいて, その全域木上で標準ラ(2)204

この遷移確率行列に従えば, グラフ $G$ のどの頂点から出発してもハミルトン閉路を一周すればどの頂点にも到達できるので, 到達時間及び全訪問時間は $n-1$ である. 本発表ではハミルトングラフでのランダムウォークを基に, 閉路を利用してランダムウォークを高速化することができることを示す.

手順 2: グラフ $G$ から両端のみが閉路 $C$ に含まれる路の頂点を($P_{0}$$v_{1},$$V_{R}$, ER)(頂点数恥) を選ぶ. 両端とし, 路上の頂点が$v_{n0}\in V_{C}$$v_{1}arrow v_{2}arrow\cdotsarrow v_{n_{0}}(v_{i}\in V_{R}$: $i=1,2,$$\cdots,$ $n_{0})$(5)のように並んでるとする. ここで路
$e_{(i_{1}t+1)}(1\leq i\leq n_{c}-1)$$P_{0}$

上の辺にたいして以下のように向き付けを行う.

2.2閉路循環向き付け(6)$e:varrow v_{i+1}$

221

定義

ここで $G$ の部分グラフ $G’=(V’, E’)$ を以下の強連結グラフになるように無向グラフの辺に向きを付けることを閉路循環向き付けと定義する. また全ての無向グラフでこの向き付けが存在するとは限らない.

222
可能.

証明

任意の 2 点連結無向グラフ $G=(V, E)$ に対して, 以下手順で各辺に向き付けをした有向グラフ$G’$ を生成する.

$i=1,2,$$\cdots,$(7)手順 3:グラフ $G$ から両端のみが $G’$ に含まれ$\cup P_{\dot{*}}$

任意の 2 点連結グラフで閉路循環向き付けが

手順 1:グラフ$V’=V_{C}\cup V_{R},$ $E’=E_{C}\cup E_{R}$ている路培を選び, 手順 2 と同様にして辺の向を新たに $G’$ とする. $V=V’$
きを決め,G’補題 21$(|V_{C}|=n_{c})$ように決める.

$G$から任意の閉路 $C(V_{C}, E_{C})$ :を選び, 閉路 $C$ において,として,$v_{i}\in V_{C}$となるまでこの操作を繰り返す. 2 点連結グラ
フでは部分グラフ $G’$ に路疏が接続しているとき, 必ず路の両端が接続している. 路の片方の端点しか接続していなければ, 唯一の接続点を取り除けばグラフが非連結となり,2 点連結グラフではない口

22.3

補題 22

閉路循環向き付けで生成された有向グラフは: 強連結である.

$n_{c}$

証明$v_{1}arrow v_{2}arrow\cdotsarrow v_{n_{\epsilon}}arrow v_{1}$(3)のように頂点が並んでいるとする. ここで閉路 $C$上の頂点 $v_{i},v_{i+1}$ 間の辺 $e_{(i,i+1)}(1\leq i\leq n_{c}-1)$および頂点間の辺ように向きを付ける.
$v_{n_{c}},$$v_{1}$$e_{(n_{\text{。}},l)}$に対して以下の帰納法により証明する. まず手順 1 で向き付けされた閉路 $C$ が強連結であることは自明である.
手順 2-3 でグラフ $G’$ に路 $P_{j}(i\geq 0)$ が付加された

場合, 強連結であると仮定し, 新たに路$P_{i+1}$を付加する場合でも強連結性が保たれることを示す.
路上の頂点 $vj,$ $v_{k}\in Vp_{i+1}$ において,j $<k$
$P_{i+1}$$\{\begin{array}{l}e_{(i,i+1)};v_{i}arrow v_{i+1}e_{(n_{c},1)}:v_{n_{C}}arrow v_{1}\end{array}$(4)であれば路$P_{i+1}$

上を$v_{j}arrow v_{j+1}arrow...$グラフ$G$の頂点が全て閉路ここで終了する. .

$C$に含まれていればと遷移することで吻から
特に$v_{1}$$v_{k}$$arrow v_{k}$(S)は到達可能であり,からは路 $P_{i+1}$ 上の全ての頂点に到達可205能であり,vni l へは路上の全ての頂点から到達可能である. $G’$ は強連結なので $G’$ 上の任意の頂点から $v_{1}\in V’\cap P_{i+1}$ は到達可能であるので, 路 $P_{i+1}$ 上の全ての頂点へも到達可能である.
また $G’$ の強連結性にょり,vn:
ら$G’$

311

$P_{i+1}$$+$$+$

l$\in V^{l}\cap P_{i+1}$

直列操作

2 つの TTLG $((V_{1}, \text{ _{}1}), s_{1}, t_{1}),$ $((V_{2},$ 坊 $), s2, t_{2})$醒

に対してTTLGか上の全ての頂点に到達可能なので,Pi l 上ここで

$t_{1}$$=$$s_{1}$

で直列操作を行うと,$(((V_{1}\cup V_{2}, E_{1}\cup E_{2}), s_{1},t_{2})$$V_{1}\cap V_{2}=\{t_{1}\}$が得られる.

である.

$+$の任意の頂点から $G’$ 上の全ての頂点へ到達可能である. 以上より, 路上の頂点 $vj$ , vk V 高において,j $>k$ の場合でも $vjarrow\cdotsarrow v_{n_{1+1}}arrow$( $G’$ ’ 上の頂点)と遷移するこvlとで吻から }よ到達可能である. 以上よりど$P_{1+1}$$arrow$$arrow$

.. .

$\in$

$arrow v_{k}$$v_{k}$の 2 頂点間もお互いに到達可能であり,P$*\cdot+$l を加えた $G’$ も強連結性が保たれている口

23

閉路を利用したランダムウォーク

2 点連結グラフ $G=(V, E)$ に閉路循環向き付けをして得られる有効強連結グラフ $G’=(V,E’)$に対し, 次のように頂点 $v_{i}\in V$ から $vj\in V$ への遷移確率を決める.
$p_{1j}=\{\begin{array}{l}\frac{l}{out\deg(v_{i})}(e_{(}i,j)\in E’)0(\text{その}ffi)\end{array}$outdeg(vi):頂点$v_{i}$(9)の $G’$ における出次数

3.2

直並列操作の拡張$:|$

この遷移確率行列に従うランダムウォークで直列操作, 並列操作を拡張した $S*$ 操作,P 操
は 2 点連結グラフを構成する路の数が定数であれ作を定義する. これらの操作により得られるグ
ば, $O(n)$ の全訪問時間を達成できる, しがしながら一般の 2 点連結グラフに対しては $o(n^{2}\log n)$ ラフは直並列グラフである.
$*$$\{$の全訪問時間となる.

3.21$\backslash *$32 点連結な直並列グラフ

31

直並列グラフ

$S*$操作

グラフ $G=(V, E)$ に新しく頂点 $w$ を追加
1 , 辺 $(u, v)\in E$ を取り除く. そして新たに辺し$w),$ $(w,v)$ を追加する.

$($$\ovalbox{\tt\small REJECT} u,$

直並列グラフとは, 直列操作と並列操作という2 つの操作により再帰的に構成できるグラフである. 2 つの端点に $s,$ の識別子が付けられた
グラフ (two-terminal labeled graph TTLG) を$t$と表す. ここで $G=(V,E)$ は多重グラフである. また最小の TTLG は 2 つの頂点とそ$(G, s, t)$れを結ぶ 1 つの辺からなるグラフである.

$rightarrow$$b$–

206

322

$P*$

(2) 粒子の遷移の方向はある閉路循環向き付けに操作

グラフ $G=(V, E)$ 上の辺をなす 2 頂点 $u,$ に対し, 辺 $(u, v)$ を 1 本迫加する. $((u, v)$ は多重辺$v$となる)

従う.
(3) 頂点$-$から$u$

3.3$D$への遷移確率に従ったパスが存(4) 頂点 から への遷移確率に従ったパスが存在して, 全てが $B$ に包含されていない(5) 頂点 では粒子が の確率で $B$ に属する頂
$u$

$v$

$rightarrow$$v$

在して, 全てが $B$ に包含されている.

$O$$u$$\frac{1}{f}$点に遷移する.

2 点連結グラフとの関連多重グラフが直並列グラフであることと, その多重グラフの 2 点連結成分が閉路に $S*$ 操作と$P*$ 操作を繰り返して得られることが等価であることが知られている. このことから多重グラフが二点連結な直並列グラフならば, その多重グラフが閉路に $S*$ 操作と $P*$ 操作を繰り返して得られることと等価である.

このとき $B(u,v)$ に対して, 以下のパラメータを定義する.
$c(B)$ : 粒子が部分グラフ $B(u,v)$ の頂点を全て訪問するまでに, 頂点 を通過する回数の期待値.
$t(B)$ : 頂点 $u|’$. ある粒子が部分グラフ $B(u, v)$ 上のパスを通り, 頂点 に到達するまでの遷移数の期待値.
本のパスがあり, それぞれの路の長さ$u,v$ 間にの平均が であるとき, 以下のようになる.
$u$

$v$

$r$

$l$

42 点連結な直並列グラフ上のランダムウォークの高速化$c(B)=rH_{r}$$=r \sum_{i=1}^{r}\frac{1}{i}$直並列グラフのグラフ構造は再帰的に定義されているため, グラフを部分構造に分割し, 再帰的にグラフの遷移確率行列を決定していく.

$\sim r\log r$$t(B)=l$$B(u, v)$ に含まれる頂点数を $n_{B}$ とする.

4.1

2 点連結な直並列グラフの基本構造

このとき $B(u, v)$ に含まれる $u-v$ パス $i(1\leq$で, その長さ が閾値 $\psi_{B}$ より短いものについて, 次のようにパス 上の頂点での遷移確$i\leq r)$

2 点連結な直並列グラフの基本構造を 2 点 $u,$$v$とそれらを結ぶ $r(\geq 1)$ 本のパスからなる無向グラフと定義し,B $(u, v)$ と表す.

$l_{i}$$i$

率を変更する.
パス 上の頂点を 側からる. ただし $w_{i}^{0}=u,w_{i}^{l_{i}}=v$ である.
(1)
$i$

$u$

$w_{i}^{0},w_{i}^{1},$$\cdots,w_{i^{I}}^{l}$とす$P(w_{i}^{0},w_{i}^{1})= \frac{1}{i}$(2) $P(c\dot{d}_{i}, \iota\dot{d}_{i}^{+1})=\pi 1,(1\leq j\leq l_{i}-2)$(3)(4)(5) $P(w_{i^{i}}^{l-1},w_{i}^{l_{i}-2})=1$$P(w_{i^{t}}^{l-1},w_{1}^{l_{i}}\cdot)=0$$P(\uparrow\dot{d}_{i},\tau\dot{d}_{i}^{-1})\approx^{1}B(1\leq j\leq l_{i}-2)$

無向な直並列二点連結グラフ $G(V, E)$ が基本構
造 $B(u, v)$ を含み,B $(u, v)$ が頂点 u,v のみで $G$ の他の部分と接続しているとする.
$G$ 上で以下を満たす遷移確率行列を考える.
(1) 粒子は現在の頂点に滞在しない.

このような遷移確率の変更が行われたパスを髭と呼ぶ. また閾値以上の長さのパスを髭に変更する操作をパスの切断と呼ぶ.

207ている.

(2) 頂点$v\ovalbox{\tt\small REJECT}^{}r$いる.

(3) 番目の道グラフを$i$で, 頂点がとする.

$r_{i}^{0},$$\frac{r-1}{r+1}\leq A_{i}<\frac{r}{r+1}$

本の道グラフの端末点が接続して$r_{1}!,$$r_{i}^{l_{i}}$$\ldots,$とすると, 辺の数がの順に並んでおり, $r_{i}^{0}=v$$P_{i}$

よって瓦は,$l_{i}$このとき次のような遷移確率を与える(1) $p(u, v)=1,p(v, u)=0$(2)$p(v, w)= \frac{1}{r+1},p(w, v)=0$(3)$(1\leq i\leq r)$(4)$(1\leq i\leq r,$ $1\leq j\leq$$p(v,r_{i}^{1})= \frac{1}{r+}T$$\frac{1}{2l_{i}}\leq K_{t}<\frac{1}{l_{i}}$また頂点 にある粒子が頂点 $w$ に到達するまでの遷移数の期待値 $D$ は, 以下の式で計算できる.
$u$$D= \frac{1}{r+1}+\frac{1}{r+1}\cdot(D_{1}(l_{1})+1)+\cdots+\frac{1}{r+1}\cdot(D_{1}(l_{f})+1)$$p(\dot{d}_{i},\dot{d}_{i}+1)=\Sigma 1$$l_{i}-1)$(5)$p( \dot{d}_{i}+1,\dot{d}_{i})=\frac{1}{2}$$=1+ \frac{1}{r+1}\sum_{i=1}^{r}D_{1}(l_{i})$$(0\leq i\leq r,$ $1\leq j\leq$208にある粒子が $w$ に到達
ここで,Dj(li) は頂点するまでの時間をとしており,DlOi) は以下の式で表せる.
$\dot{p}_{:}$

43

部分構造の並列操作

2 点連結な直並列グラフの 2 つの部分構造を並列に接続して新しい部分構造 $B$ を作ることを考える. このとき $B$ について以下のことが成り立つ.
(1) 髭の長さ(2) 髭に含まれる頂点数:nB 個以下(3) パスの数: n 邦 $+\sqrt{n_{B_{2}}}=O(\sqrt{n_{B}})$(4) パス長:max{nBl’}
以上より $B$ のパラメータ $c(B),t(B)$ は, 以下の$B_{1},$ $B_{2}$$D_{1}(l_{i})=D+2l_{i}+1$

よって $D$ の式から

$D_{1}(l_{i})$を消去して,$: \max\{\sqrt{n_{B_{1}}}, \sqrt{n_{B_{2}}}\}\leq\sqrt{n_{B}}$$\sqrt{}\sqrt{}$$D=1+ \frac{r}{r+1}D+\frac{r}{r+1}+\frac{2}{r+1}\sum_{i=1}^{r}l_{i}$$n_{B_{2}}$$\leq n_{B}$ようになる.

$D=1+2 \sum_{i+1}^{r}(l_{i}+1)$$c(B)=O(\sqrt{n_{B}}\log n_{B})$42

部分構造の直列操作$t(B)=O(n_{B})$2 点連結な直並列グラフの 個の部分構造を直列に接続して新しい部分構
造 $B$ を作ることを考える.
$k$$B_{1},$ $B_{2},$$\cdots,$$B_{k}$

4.4

グラフ全体の全訪問時間

頂点$B$$v$から $u$ へのパスを含む部分グラフ$G\backslash$

も直並列操作で構築でき, パラメータと同様に求まり, 全訪問時間は$c(G\backslash$$B),$ $t(G\backslash B)$ が $B$$c(B)+c(G\backslash B)$

このとき各 $B_{i}(1\leq i\leq k)$ のパラメータをとし, それらを直列に連結してできるのパラメータを $c(B),$ $t(B)$ とする. $t(B)$ は以下の式で表すことが出来る.

$c(B_{i}),t(B_{i})$$B$と $t(B)+t(G\backslash B)$ の積のオーダーで表せる.
したがって, 直並列操作で得られる頂点数$n$の2 点連結グラフでランダムウォークの全訪問時間を ( 〉nlog n) にする遷移確率行列が存在
$O$

$n$

する.
$t(B)= \sum_{i=1}^{k}t(B_{i})$5$=O(n_{B})$また $c(B)\}^{\sim}$.つ$A1$する ffl $i+nae$ を接 $m$ した ffl9nて$B_{j}$$\not\in\grave$$\ovalbox{\tt\small REJECT}h$maxi$\leq i\leq k\{c(B_{i})\}$とすると,を\S R.

$B_{j}B\backslash k\mathbb{B}i\Xi PJ\}’$

を $B*$ とすると,$c(B)\leq c(B*)$$=O(\log_{(\frac{\sqrt{n_{B_{j}}}}{\sqrt{}^{\mathfrak{n}_{B}}r^{-1}})}k\sqrt{n_{B_{j}}})$

まとめと今後の課題
本稿では 2 点連結な直並列グラフにおいて全訪問時間が $0(n\sqrt{n}\log n)$ を達成するような遷移確率行列が存在することを示した. しかしながら 2 点連結グラフ全般に対して, 全訪問時間がより高速なランダムウォークを実現する遷移確率行列は分かってなく,2 点連結グラフ上のランダムウォークの高速化の実現, もしくは全$O(n^{2})$

訪問時間がであることの証明が今後の研究課題として挙げられる.
$\Theta(n^{2})$$=O(\sqrt{n_{B_{f}}}\log k\sqrt{n_{B_{j}}})$$=O(\sqrt{n_{B}}\log n_{B})$

209

参考文献
[1] D.J.Aldous: “On the time taken by random
walks on finate groups to visit every state”,
Z. Wahrsh. verw. Gebiet, Vol. 62, pp. 361-393,

1983.

[2] R.Aleliunas,R. $M$

Karp,R.J.Lipton,L.Lovaasz,andC.Rackoff:“Random walks, universal traversal sequences,and the complexity of maze problems”,
Proc.20th Ann.Symposium on Foundations ofComputer Science, pp. 218-223, 1979.
[3] Satoshi Ikeda, Izumi Kubo, Norihiro Okumoto, and Masafumi Yamashita: “Impactof Local Topological Information on Random
Walks on Finate Graphs”, Proceedings of Thirtieth Intemational Colloquium on Automata,
Languages and Programming, pp. 1054-1067,
2003.