局所情報を利用するグラフ上のランダムウオークのカバータイムについて

スポンサーリンク

概要

論文の詳細を見る
有限グラフ上で隣接する頂点に等確率で遷移するランダムウォークのカバータイムは,グラフの頂点数をnとするときO(n^3)となることが知られている.このとき,隣接する頂点に等確率で遷移するという規則は,グラフ全体の接続情報を保持しないという状況を反映したものであると考えられる。よって,頂点の接続関係の局所情報を利用できる場合は,より望ましい遷移確率の規則を設計出来る可能性がある。本稿では,著者たちが提案した遷移確率行列P=(Puv)を用いるとカバータイムがO(n^2 log n)となることを示す。ここで,N(u)を頂点uに隣接する頂点の集合,deg(u)を頂点uの次数とすると,Pとは,v∈N(u)ならばPuv=min{1/deg(u),1/deg(v)}また,Puu=1-Σv¬inN(u)Puvで定義されるものである。
一般社団法人情報処理学会の論文
2002-09-19

著者

関連論文

もっと見る

スポンサーリンク