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

• Item type: SIG Technical Reports(1)
• 公開日: 2002-09-19
• タイトル: 局所情報を利用するグラフ上のランダムウォークのカバータイムについて
• タイトル / 言語: en
• タイトル: Local Topological Information and Cover Time
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京農工大・工
• 著者所属: 広島大学・理
• 著者所属: （株）日立・金融システム事業部
• 著者所属: 九州大学・工学部
• 著者所属(英): en
• 著者所属(英): Tokyo University of Agri. & Tech.
• 著者所属(英): en
• 著者所属(英): Hiroshima University
• 著者所属(英): en
• 著者所属(英): Hitachi, Ltd
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者名: 池田, 諭; 久保, 泉; 奥本, 哲大; 山下, 雅史
• 著者名(英): Satoshi, Ikeda; Izumi, Kubo; Norihiro, Okumoto; Masafumi, Yamashita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 有限グラフ上で隣接する頂点に等確率で遷移するRW のCT は，グラフの頂点数をnとするときO(n^3)となることが知られている．このとき，隣接する頂点に等確率で遷移するという規則は，グラフ全体の接続情報を保持しないという状況を反映したものであると考えられる．よって，頂点の接続関係の局所情報を利用できる場合は，より望ましい遷移確率の規則を設計出来る可能性がある．本稿では，著者たちが提案した遷移確率行列 P^ = (p^_{uv})を用いるとカバータイムがO(n^2 log n)となることを示す．ここで，N(u)を頂点uに隣接する頂点の集合，deg(u)を頂点uの次数とすると，P^とは，ν∈N(u)ならばp^_{uv} = min {1/deg(u) 1/deg(ν)} また，p^_{uu} = 1 - ㊥ν●N(u)}p^_{uv}で定義されるものである．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: It is just amazing that the cover time of a random walk on a finite graph, in which the vertex visited next is selected from the adjacent vertices at random with the same probability, is bounded by O(n^3) for any graph with order n, despite of the lack of global topological information. Thus a natural guess is that a better transition matrix is designable if more topological information is available. By investigating the transition matrix P^ = (p^_{uv}) proposed by Ikeda et al., this paper shows that for any graph with order n, the cover time with respect to widehat{P} is bounded by O(n^2 log n), where p^_{uv} = min {1/deg(u),1/deg(v) } for v ∈ N(u), p^_{uu} = 1 - ㊥v ∈ N(u)} p^_{uv}, and deg(u) is the degree of a vertex u.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2002, 号 88(2002-AL-086), p. 27-34, 発行日 2002-09-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会