正則有向グラフの短縮型ジグザグ積
におけるランダムウォークの収束性
野村 俊一
指導教員: 竹村 彰通 教授

2007 年 2 月 5 日をグラフ G の spectral expansion という．

概要

ここで λ(G) は A の第 2 特異値（2 番目に大きい特異

本論文ではグラフのジグザグ積を変更した新たなグラ値）となる．初期分布を y ∈ RN とおくとフの積（短縮型ジグザグ積）を提案する．ジグザグ積と||Ak y − uN || = ||Ak (y − uN )|| ≤ λ(G)k ||y − uN ||は２つの正則有向グラフから，より頂点数の大きな正則有向グラフを作る演算である．グラフ上のランダムが成り立つ．

ウォークにおける確率分布の定常分布への収束の速さ

2 正則有向グラフのジグザグ積と短縮型ジグは spectral expansion という量で表されるが，spectralザグ積の定義

expansion の小さい正則有向グラフ同士のジグザグ積はspectral expansion が小さいことが [1, 2, 3] で示されてM -正則有向グラフ G の各頂点に接続する辺にラベルいる．本論文で提案する短縮型ジグザグ積は，ジグザグ付けを行う．M -正則有向グラフ G における双方向ラベ積と比べて頂点数は等しく次数のより小さい正則有向グリングとは，G の各頂点から出る M 本の辺に 1, . . . , Mラフを作る演算である．本論文では正則有向グラフのジの番号を互いに異なるよう割り当て，各頂点に入る Mグザグ積と短縮型ジグザグ積の冪乗について，spectral本の辺にも同様に番号を割り当てることをいう．

expansion の新たな上限を導出する．

ここで，頂点集合 [N ] の M -正則有向グラフ G と，頂点集合 [M ] の D-正則有向グラフ H から，G の双方向

1 正則有向グラフと spectral expansion

z と短縮型ジグザラベリングを用いてジグザグ積 G°Hz 0 を構成する方法を述べる．
グ積 G°H

多重辺と自己ループを許す一般有向グラフを考える．
各頂点で出ていく辺と入ってくる辺がそれぞれ M 本ずz とは頂点集合 [N ] ×
グラフ G, H のジグザグ積G°H

つあるグラフを M -正則有向グラフという．頂点集合を[N ] = {1, . . . , N } とする M -正則有向グラフ G 上のラ[M ] を持ち，頂点 (v, s) ∈ [N ] × [M ] から以下の 3 ス
テップによって移ることができる頂点 (w, t) へと辺をつンダムウォークを考える．このランダムウォークの確率ないだグラフである．

def.

推移行列 A の (w, v) 成分をAwv =Step1. (v, s) のうち v は固定し，グラフ H 上の頂点 s

頂点 v から頂点 w への辺の数から出る辺をたどって s から s0 に推移させる．

M

Step2. グラフ G において頂点 v から出る s0 番目のdef.

辺が頂点 w に入る t0 番目の辺であるときに，頂点とおく．このとき，1N = (1, · · · , 1)T ∈ RN とおくdef.

(w, t0 ) に推移させる．
Step3. (w, t0 ) のうち w は固定し，グラフ H 上の頂点と，uN = 1N /N は G 上のランダムウォークの定常分N布である．x ∈ Rのユークリッドノルムを ||x|| と表t0 から出る辺をたどって t0 から t に推移させる．

す．ここで，G 上のランダムウォークの定常分布への収束速度を表す spectral expansion を定義する．

z 0 は，いま本論文で提案する短縮型ジグザグ積 G°H

定義 1 グラフ G を頂点集合 [N ] の M -正則有向グラフ

z に対して頂点集合は同じであるが，のジグザグ積 G°Hとし，G 上のランダムウォークの確率推移行列を A と辺をつなぐまでのステップを上のステップ 1,2 だけに短おく．このとき縮したものである．

z 0 は頂点集合
グラフ G, H の短縮型ジグザグ積G°H||Ax||λ(G) = max
x⊥1N ||x||def.

[N ] × [M ] を持ち，頂点 (v, s) ∈ [N ] × [M ] から以下の1

2 ステップによって移ることができる頂点 (w, t) へと辺定理 2 λ(G) ≤ α < 1, λ(H) ≤ β < 1 のときをつないだグラフである．

z0λ(G°H)= 1,Step1. (v, s) のうち v は固定し，グラフ H 上の頂点 sから出る辺をたどって s から s0 に推移させる．
Step2. グラフ G において頂点 v から出る s0 番目の辺が頂点 w に入る t 番目の辺であるときに，頂点(w, t) に推移させる．

GH321w32u1232u

束速度を示している．

(u,2)

G z’ H

4 結論

(w,3)
(w,1)

z’

2上のランダムウォークにおける k (≥ 2) 回の推移での収

(u,3)

1

v3
32

(v,2)

(u,1)

Hwz 0 k ) は，G°Hz0とを示している．また第 2 式の λ((G°H)

(v,1)

1G
1＝推移では確率分布が定常分布に近づかない場合があるこ

(w,2)

(v,3)

β).

z 0 上の長さ k の有向歩道の始点から終点へと辺をG°Hつないだグラフである．定理 2 の第 1 式は，短縮型ジグz 0 上のランダムウォークにおいて，1 回のザグ積 G°H(w,3)

3√k = 2, 3, . . .

z 0 と同じ頂点集合を持ち，z 0 k は，G°H
ここで (G°H)(w,1)

z2def.となる．ただし f 0 (α, β) = f (α,GzH

1v3z 0 k ) ≤ f 0 (α, β)k−1 ,λ((G°H)

3
12

＝

本論文では，グラフのジグザグ積を変更した短縮型ジ(w,2)(v,3)

グザグ積という新たなグラフの積を提案した．また，ジ(v,1)
(v,2)

(u,3)

1

グザグ積の spectral expansion の新たな上限と，短縮型(u,1)

ジグザグ積の冪乗の spectral expansion の上限を導出(u,2)

した，本論文で示したジグザグ積の spectral expansionz （上）と短縮型ジグザグ積
図 1 ジグザグ積 G°Hの上限は，[1, 2, 3] で示された上限の一部よりも強いもz 0 （下）の様子．グラフ G は一部のみ示し，各頂G°H点に接続する辺には {1, 2, 3} より番号が与えられている．グラフ H はその番号と同じ頂点集合を持つグzラフである．ジグザグ積 G°Hと短縮型ジグザグ積
z 0 の頂点集合は，図のように G の各頂点に H のG°Hのである．短縮型ジグザグ積については，短縮型ジグザグ積自体の spectral expansion は最悪の 1 となるが，短縮型ジグザグ積を冪乗したグラフの spectral expansionの上限を導出した．
今後の課題として，定理 1 の証明を改良することにより，さらに上限を低くできるかどうかを考えたい．

頂点集合を埋め込んだ形となっている．また辺については，それぞれ頂点 (v, 1) から出る辺のみ表示している．図の破線はそれぞれの辺をつなぐまでのステップ
Step1.

Step2.

参考文献

Step3.

（ジグザグ積なら (v, 1) −→ (v, 3) −→ (w, 2) −→(w, 1) など）を示している．

[1] O. Reingold, L. Trevisan and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs.
L problem. Technical Report TR05-022, Electronic
Colloquium on Conputational Complexity (ECCC),
2005.
[2] O. Reingold, L. Trevisan and S. Vadhan. Pseudorandom walks on regular digraphs and the RL vs.
L problem. Proceedings of the 38th ACM Symposiumon Theory of Computing, (STOC 2006) 2006, pp.457466.
[3] O. Reingold, S. Vadhan and A. Wigderson. Entropywaves, the zig-zag graph product, and new constantdegree expanders. Annals of Mathematics, Vol.155,
No.1, 2001, pp.157-187. Extended abstract in FOCS
2000.

3 ジグザグ積と短縮型ジグザグ積の spectral
expansion の上限
正則有向グラフのジグザグ積と短縮型ジグザグ積のspectral expansion は，それぞれ次のように上から抑えられる．
定理 1 λ(G) ≤ α < 1, λ(H) ≤ β < 1 の と きzλ(G°H)≤ f (α, β) となる．ただし(f1 (α, β), if 2α + β ≤ 1
def.
f (α, β) =f2 (α.β), if 2α + β > 1
def. pf1 (α, β) =α(1 − β 2 )(α + β) + β 2 ,def.

f2 (α, β) = β 2 + (1 − β) ×p
α2 +β 2 min{1+α, 2−α2}+αβmin{2, 1+2α}.
2