自己ループ確率の除去による メトロポリスウォークの高速化 西関研究室 ９５２４ 近藤啓介 2015/9/30 1 はじめに インターネット,センサネットワークが発展 • 記憶しきれない程大規模 • 動的に変化する 全体を記憶しきれない “ランダム”な探索 2015/9/30 2 ランダムウォーク v Vから出発する． 2. v の隣接頂点v N v をランダムに選択し , v に推移する． 3. v に対しても 2.と同様の操作を行い， 以下同様に繰り返す． 1. ある頂点 0 0 1 0 1 1 探索時間は速いほうが良い 0.2 0.3 1 0.3 0.5 0.7 0.5 3 0.4 0.6 2015/9/30 2 0.5 G 4 0 0.3 0 0.7 0.2 0 0.3 0.5 P 0 0.4 0.6 0 0.5 0.5 0 0 3 ランダムウォークの速さ 到達時間（hitting time） 𝐻G 𝑃; 𝑢, 𝑣 : 頂点𝑢から始まるランダムウォークが初めて 頂点𝑣に到達するまでに必要な遷移数の期待値 𝐻𝐺 𝑃 = max 𝐻𝐺 (𝑃; 𝑢, 𝑣) 𝑢,𝑣∈𝑉 全訪問時間（cover time） 𝐶𝐺 (𝑃; 𝑢): 頂点𝑢から始まるランダムウォークが𝐺のすべての頂点 を訪れるために必要な遷移数の期待値 𝐶𝐺 𝑃 = max 𝐶𝐺 (𝑃; 𝑢) 𝑢∈𝑉 2015/9/30 4 単純ランダムウォーク 1/3 ½ 1 2 1/3 ½ 1/3 ½ 3 1 ½ 4 0 1/ 2 0 1/ 2 1 / 3 0 1 / 3 1 / 3 P 0 1 0 0 1 / 2 1 / 2 0 0 G 𝐻𝐺 𝑃 = 𝑂 𝑛3 , 𝐶𝐺 𝑃 = 𝑂(𝑛3 ) ※nは頂点数 2015/9/30 Lollipopグラフ 5 定常分布 遷移行列𝑃に対して 𝜋𝑃 = 𝜋 を満たす頂点上の確率分布 𝜋 = (𝜋1 , 𝜋2 , … , 𝜋𝑛 )を𝑃の 定常分布という 2015/9/30 6 メトロポリスウォーク • Metropolis-Hastings法に基づく -Markov Chain Monte Carlo(MCMC)の手法 -𝜋（定常分布）を任意に設定可能 -隣接頂点の情報を利用 1 𝑑𝑢 𝜋 𝑣 min ,1 𝑑𝑢 𝑑𝑣 𝜋 𝑢 𝑝𝑢𝑣 = 1− 𝑝𝑢𝑤 if 𝑣 ∈ 𝑁 𝑢 , 𝑑𝑢 : 𝑢の次数 𝑁 𝑢 : 𝑢の隣接頂点の集合 if 𝑣 = 𝑢, 𝑤∈𝑁(𝑢) 0 2015/9/30 otherwise. [W.K Hastings, 1970] 7 メトロポリスウォークの速さ 2 到達時間 : 𝑂 𝑓𝑛 2 全訪問時間 : 𝑂 𝑓𝑛 log 𝑛 ただし, 𝑓 = max 𝜋𝑢 / 𝜋𝑣 𝑢,𝑣∈𝑉 Glitter star グラフ [Y.Nonaka, 2009] ※nは頂点数 • 単純ランダムウォークは 𝐻𝐺 𝑃 = 𝑂(𝑛3 ), 𝐶𝐺 𝑃 = 𝑂(𝑛3 ) 2015/9/30 8 メトロポリスウォークの改善点 1 𝑑𝑢 𝜋 𝑣 min ,1 𝑑𝑢 𝑑𝑣 𝜋 𝑢 𝑝𝑢𝑣 = 1− 𝑝𝑢𝑤 if 𝑣 ∈ 𝑁 𝑢 , if 𝑣 = 𝑢, 𝑤∈𝑁(𝑢) 0 otherwise. • 同じ点にとどまることもあり,それが自己ループで 表される • 高速なランダムウォークの実現という意味では自 己ループは不要 2015/9/30 9 新しい遷移確率の提案 メトロポリスウォークの遷移確率の定義式 min 𝑝𝑢𝑣 = 1 1 , 𝑑𝑣 𝑑𝑢 1− 𝑝𝑢𝑤 すべての頂点の定常分布を 1 とする 𝑛 if 𝑣 ∈ 𝑁 𝑢 , if 𝑢 = 𝑣, 𝑤∈𝑁(𝑢) 0 otherwise. 新しい遷移確率の定義式 𝑝′𝑢𝑣 2015/9/30 𝑝𝑢𝑣 = 1 − 𝑝𝑢𝑢 0 if 𝑣 ∊ 𝑁 𝑢 , otherwise. 10 新しい遷移確率 𝑝′𝑢𝑣 = 1 1 min , 𝑑 𝑣 𝑑𝑢 1 1 𝑤∈𝑁(𝑢) min 𝑑 , 𝑑 𝑤 𝑢 0 𝑣∊𝑁 𝑢 , otherwise. • メトロポリスウォークにおいて自己ループをカ ウントしない場合と等価 2015/9/30 11 シミュレーション1 • 頂点数が21～401個のGlitter starグラフ • 中心から出発し,全頂点を訪問するまでの移 動回数と自己ループ回数を求める • 1000回の試行の平均 Glitter starグラフ 2015/9/30 12 Glitter starグラフでシミュレーション 総移動回数 移 動 回 数 頂点数 図1: メトロポリスウォーク 2015/9/30 13 Glitter starグラフでシミュレーション 総移動回数 自己ループ 総移動回数 移 動 回 数 移 動 回 数 頂点数 図1: メトロポリスウォーク 頂点数 図2 : 新しいランダムウォーク • 総移動回数の約半分が自己ループ • 新しいランダムウォークでは,既存のメトロポリス ウォークの総移動回数は約半分 2015/9/30 14 シミュレーション2 • 頂点数が50～400個のBAモデルに基づく グラフ • 完全グラフから出発し,全頂点を訪問するまで の移動回数と自己ループ回数を求める • 1000回の試行の平均 2015/9/30 15 頂点𝑛に基づく BAモデルに基づくグラフ 1. 𝑚個の完全グラフK m から始める 2. 新しい頂点を追加し、既存の頂点に対して 次数に比例する確率で辺を張る 3. 𝑛個なるまで2を繰り返す BAモデルに基づくグラフ 2015/9/30 16 BAモデルに基づく グラフでシミュレーション 総移動回数 移 動 回 数 頂点数 図3: メトロポリスウォーク 2015/9/30 17 BAモデルに基づく グラフでシミュレーション 総移動回数 自己ループ 総移動回数 移 動 回 数 移 動 回 数 頂点数 図3: メトロポリスウォーク 頂点数 図4: 新しいランダムウォーク • 自己ループを起こしやすいグラフ • 新しいランダムウォークでは約4倍高速 2015/9/30 18 考察 • 自己ループを除去することによって自己ループ の分だけ高速にすることができる • 次数が大きい頂点と次数が小さい頂点が隣り 合っているグラフでは自己ループが起こりやす いと言える • BAモデルに基づくグラフでは,辺の両端点の次数 の差が大きいので,自己ループを除去することに よって効果的である 2015/9/30 19 今後の課題 • 今回扱っていないグラフ,特に現実に現れる ネットワークに対して検証を行うこと • 新しいランダムウォークが既存のメトロポリス ウォークと比べてどの程度速くなるか理論的 な解析を行うこと 2015/9/30 20 予備スライド 2015/9/30 21 Glitter starグラフでの 移動回数と自己ループの比率 • 頂点数の増加に伴い自己ループが増加している • 自己ループの割合は約5割で収束している 2015/9/30 22
© Copyright 2024 ExpyDoc
![[Vol.A07] ULTRON ES-PhCD (LC/MS用光学異性体分離セミミクロカラム)](http://s1.expydoc.com/store/data/006103779_1-c8a9c044ea7ee25f27dc36343095978f-250x500.png)
