ランダムウォークの再帰時間を用いたグラフ情報推定

ランダムウォークの再帰時間を
用いたグラフ情報推定
西関研究室
9575
戸口七美
2015/10/1
1
動機
頂点数も辺数もわからないグラフ
Ex) インターネット、アドホックネットワーク
トークンが戻ってくるまでの時間を
使ってグラフ情報を推定
2015/10/1
2
ランダムウォーク
１
• グラフG  (V , E )上の頂点を遷移
• 遷移確率行列𝑃に従う
0.1
例えば…
 0 0.2 0.2 0 0.6
 0.1 0 0.6 0 0.3


P   0 .8 0.2 0 0 0 


 0 0 0 0 .6 0.4 
0.3 0.2 0 0.5 0 
2015/10/1
２
0.2
0.2
0.6
0.6
0.3
0.8
３
0.2
0.2 0.3
0.6
４ 0.4
0.5 ５
3
幅優先探索との比較
１
２
４
点の名前？
訪問済み？
３
５
６
７
グラフの全体像を把握しておく
必要がある
ランダムウォークでは
１つ１つ点を記憶しておく必要がない
2015/10/1
4
単純ランダムウォーク
１
• 等確率で次に訪問する点を決定
1
3
1
3
1
3
1
2
1
31
２
 1

puv   d u
0

v  N u とき 
1 3
3
それ以外 
※𝑑𝑢 はグラフ𝐺での𝑢の次数
2015/10/1
1
2
４ 1
1
3
1
3
３
1
3
５
5
定常分布
• 遷移確率行列𝑃に対して
P  
を満たす確率分布 を定常分布と呼ぶ
- 各頂点が訪問される割合を表す
2015/10/1
6
メトロポリスウォーク
P  
与えられた頂点上の定常分布𝜋 = (𝜋1, 𝜋2, ⋯ 𝜋𝑛, )
に対して𝑢から𝑣の遷移確率𝑝𝑢𝑣 が




1


d

min  u v ,1 v  N u の場合 
d u
d


v u




v  uの場合 

puv 1   puw
 wN ( u )
0
それ以外 


※𝑑𝑢 はグラフ𝐺での𝑢の次数

どこの頂点にどれくらいの割合でいるか設定可能
2015/10/1
7
再帰時間 H G P; u, u 
頂点𝑢を出発したトークンが
再び頂点𝑢に戻ってくる遷移数の期待値
また
H P; u, u  
G
1

u
S. Ikeda, I. Kubo, M. Yamashita, ‘’The hitting and cover time of randam walks on finite
graphs using local degree information,’’ Theoretical Computer Science(2009), pp.94100.
2015/10/1
8
H G ( P; u , u ) 
1
u
を用いたグラフ情報推定
• 単純ランダムウォーク
d u ここで mは辺数 より

u
2m
du
du
m≒

H G ( p; u , u ) 辺数がわかる
2 u
2
• メトロポリスウォーク
 の値を任意に設定可能
1
→  u  に設定
n
1
𝑛≒
= 𝐻𝐺 (𝑃; 𝑢, 𝑢)
𝜋′𝑢
2015/10/1
点数がわかる
9
課題
• 再帰時間は期待値であり，実際の遷移数は
期待値通りではない．
→何回も試行して平均をとる．
→シミュレーションを行い，真の値に近い
値を得るための試行回数を明らかにする．
2015/10/1
10
2015/10/1
11
辺数推定について
𝜋
×
𝜋
=
𝑃
𝑢
𝑛
𝑛
𝜋𝑖 × 𝑃𝑖𝑢 =
𝑖=1
𝑖𝜖𝑁(𝑢)
𝑑𝑢
× 𝑃𝑖𝑢
2𝑚
𝑛
=
𝑖𝜖𝑁(𝑢)
𝑑𝑖
1
×
2𝑚 𝑑𝑖
𝑑𝑢
=
2𝑚
2015/10/1
12
メトロポリスウォークでの点数推定
𝜋の値を任意に設定することができる
↓
1
 'u  に設定
n




1


d
u

min
,1 v  N u の場合 
d


d 



v  uの場合 

p 1   p
v
u
uv

0



wN ( u )
v
u
uw
それ以外 
約分できるので𝑛の値がわからなくても点数がわかる
2015/10/1
13
H G ( P; u , u ) 
1
u
を用いたグラフ情報推定
• 単純ランダムウォーク
d u ここで mは辺数 より

u
2m
du
du
m≒

H G ( p; u , u ) 辺数がわかる
2 u
2
• メトロポリスウォーク
 の値を任意に設定可能
1
→  u  に設定
n
1
𝑛≒
𝐻𝐺 (𝑃; 𝑢, 𝑢)
𝜋′𝑢
2015/10/1
点数がわかる
14
幅優先探索とランダムウォークの比較
2015/10/1
ランダムウォーク
幅優先探索
頂点の名前
不要
必要
必要な領域(bit)
log fn
(n  m) log n
15
到達時間と全訪問時間
• 到達時間 𝐻𝐺 (𝑃; 𝑢, 𝑣)
- 頂点𝑢から出発したランダムウォークが
初めて頂点𝑣を訪問するまでに要する遷移数
の期待値
• 全訪問時間 𝐶𝐺 𝑃; 𝑢
- 頂点𝑢から出発したランダムウォークが
グラフ𝐺上の頂点全てを訪問するまでに要する
遷移数の期待値
2015/10/1
16
ランダムウォークの速さ
到達時間
 
 
単純ランダムウォーク
n
メトロポリスウォーク
 f n 
ここで
全訪問時間
3
 u
f  maxu ,vV 
 v
2
n
3

 f
n
2
log n



Y. Nonaka, H. Ono, K. Sadakane, M. Yamashita, ‘’The hitting and cover time
Metropolis walks,’’ Theoretical Computer Science(2010), pp.1889-1894.
2015/10/1
of

17

Download Report