[チュートリアル講演]局所情報を用いる有限グラフ上の乱歩のヒッティング時間とカバー時間

スポンサーリンク

概要

論文の詳細を見る
連結な無向グラフG=(V,E)上で遷移確率行列P^<(β)>=(p^<(β)>_<uv>)_<u,v∈V>がu∈V,v∈N(u)に対してp^<(β)>_<uv>=(exp[-βU(u,v)])/(Σ_<w∈N(u)>exp[-βU(u,w)])で定まる乱歩を考える.ここで,βは実数のパラメータ,N(u)はu∈Vの隣接頂点の集合,deg(u)=|N(u)|,かつUはポテンシャル関数でu∈V,v∈N(u)に対してU(u,v)=log(max{deg(u),deg(v)})とする.本稿ではP^<(1)>に対する次数nの連結グラフのヒッティング時間とカバー時間がそれぞれO(n^2)およびO(n^2 log n)であることを示す.次数nの線グラフの最大ヒッティング時間が,任意の遷移規則に対してΩ(n^2)を必要とすることから,P^<(1)>はヒッティング時間に関して最適な遷移規則であることを意味している.
社団法人電子情報通信学会の論文
2003-07-25

著者

関連論文

もっと見る

スポンサーリンク