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

ランダムウォークの再帰時間を
用いたグラフ情報推定
西関研究室
9575
戸口七美
2015/10/1
1
動機
頂点数nも辺数mもわからないグラフ
Ex) インターネット、アドホックネットワーク
トークンが戻ってくるまでの時間
(再帰時間)を使ってグラフ情報
(点数𝑛や辺数𝑚)を推定
2015/10/1
2
ランダムウォーク
• グラフ上の頂点を遷移
• 遷移確率行列𝑃に従う
例えば…
 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.1
0.6
２ 0.3
0.8
３
0.2
0.2 0.3
0.6
４ 0.4
0.5 ５
3
幅優先探索との比較
１
２
４
点の名前？
訪問済み？
３
５
６
７
グラフの全体を表現するデータ
構造が必要である
ランダムウォークでは
点の名前を記憶しておく必要がない
2015/10/1
4
単純ランダムウォーク
• 等確率で次に訪問する点を決定
 1

puv   d u
0

※𝑑𝑢 はグラフ𝐺での𝑢の次数
2015/10/1
1
3
1
3
1
3
1
2
1
31
v  N u とき 
それ以外 
１
２
1
2
1 3
3
４ 1
３
1
3
1
3
1
3
５
5
定常分布
• 遷移確率行列𝑃に対して
P  
を満たす確率分布 
を定常分布と呼ぶ
 ( 1 ,  2 , ,  n )
u
- 𝜋𝑢 は各頂点𝑢が訪問される割合を表す
2015/10/1
6
メトロポリスウォーク
与えられた頂点上の定常分布𝜋 = (𝜋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 G P; u, u  
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
点数𝑛が推定できる
計算機実験
頂点数
パス
100, 500
サークル 100,500
格子
20×20
100
完全
全体の頂点数
lollipop 100
(完全グラフの頂点数
10,30,50)
BAモデル
全体の頂点数
100
(最初の完全グラフの
頂点数5,10,50)
2015/10/1
10
Lollipopグラフ
・・・
頂点数 100
完全グラフの頂点数
10, 30, 50
2015/10/1
11
実験結果（Lollipop, 辺数𝑚）
パスの頂点数:50
1275
2015/10/1
パスの頂点数:70
505
パスの頂点数:90
135
12
実験結果(Lollipop 頂点数𝑛)
パスの頂点数:50
2015/10/1
パスの頂点数:70
パスの頂点数:90
13
計算結果まとめ
頂点数
パス
サークル
格子
完全
lollipop
BAモデル
2015/10/1
収束する試行回数
頂点:4300, 辺:12500
100, 500
100,500 頂点:2200, 辺:28100
20×20 頂点:2700, 辺:1400
頂点:100, 辺:20
100
全体の頂点数100
(完全グラフの頂点数10,30,50)
全体の頂点数100
(完全グラフの頂点数
5,10,50)
頂点:4000, 辺:2000
頂点:1500, 辺:1600
14
今後の課題
• 他の種類のグラフでもシミュレーションを行う
• 今回は実験で結果を得たが,
今後の課題は理論的な解析をすること
2015/10/1
15
2015/10/1
16
単純ランダムウォークでの
辺数推定について
𝜋
𝑃
×
𝜋
=
𝑢
𝑛
𝑛
𝜋𝑖 × 𝑃𝑖𝑢 =
𝑖=1
𝑖𝜖𝑁(𝑢)
𝑑𝑢
× 𝑃𝑖𝑢
2𝑚
𝑛
=
𝑖𝜖𝑁(𝑢)
𝑑𝑖
1
×
2𝑚 𝑑𝑖
𝑑𝑢
=
2𝑚
2015/10/1
17
メトロポリスウォークでの点数推定
𝜋の値を任意に設定することができる
↓
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
18
シミュレーション（パスの時）
↑
始点
ランダムウォークの再帰時間を用いて頂点数を
求める.
↓
何回も繰り返し、平均をとる.
※今回は試行回数10万回
2015/10/1
19
実験結果(パス頂点数100)
du
m
H G ( P; u , u )
2
2015/10/1
より
1
m  H G ( P; u , u )
2
20
シミュレーション（サークルの時）
2015/10/1
21
実験結果（サークル頂点数100）
du
m
H G ( P; u , u )
2
2015/10/1
du
H G ( P; u , u )
より m 
2
22
シミュレーション（格子グラフの時）
2015/10/1
23
実験結果（格子グラフ辺数）
2n(n-1)の辺、20×20の格子グラフでは760
du
2
m
H G ( P; u , u ) より m  H G ( P; u , u )
2
2
2015/10/1
24
実験結果（格子グラフ頂点数）
頂点数20×20の格子グラフにおける頂点数を推定
2015/10/1
25
完全グラフ
頂点数20の完全グラフにおいて
シミュレーションを実行する.
2015/10/1
26
実験結果（完全グラフ辺数）
辺数は20×10＝200
頂点数20の完全グラフなので頂点数は20×19=190
du
20
m
H G ( P; u , u ) より m 
H G ( P; u , u )  10 H G ( P; u , u )
2
2
2015/10/1
27
実験結果（完全グラフ頂点数）
頂点数20
2015/10/1
28
Lolipopグラフ
2015/10/1
29
実験結果（lollipop 辺数）
2015/10/1
30
実験結果(lollipop 頂点数)
2015/10/1
31
実験結果(BAモデル辺数)
2015/10/1
32
実験結果（BAモデル頂点数）
2015/10/1
33
実験結果（パス頂点数500）
頂点数が多い方が収束するまでに時間がかかる.
2015/10/1
34
実験結果（サークル頂点数500）
2015/10/1
35
幅優先探索とランダムウォークの比較
2015/10/1
ランダムウォーク
幅優先探索
頂点の名前
不要
必要
必要な領域(bit)
log fn
(n  m) log n
36
到達時間と全訪問時間
• 到達時間 𝐻𝐺 (𝑃; 𝑢, 𝑣)
- 頂点𝑢から出発したランダムウォークが
初めて頂点𝑣を訪問するまでに要する遷移数
の期待値
• 全訪問時間 𝐶𝐺 𝑃; 𝑢
- 頂点𝑢から出発したランダムウォークが
グラフ𝐺上の頂点全てを訪問するまでに要する
遷移数の期待値
2015/10/1
37
ランダムウォークの速さ
到達時間
 
 
単純ランダムウォーク
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

38

Download Report