| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2022-12-13 10:40 動的グラフにおいてランダムウォークの怠惰性がグラフ探査の効率性に与える影響 ○中川大輝・岩田丈了・松尾涼太郎・大崎博之（関西学院大）  IA2022-57 |
|
| 抄録 | （和） | ランダムウォークを用いたグラフ探査は幅広い用途への工学的な応用が可能であり、その数理的な特性が 活発に研究されている。近年、静的な (時間とともに変化しない) グラフ上のランダムウォークだけではなく、動的な (トポロジ構造が時間とともに変化する) グラフ上のランダムウォークが注目を浴びている。これまでに、動的グラフ の一種である進展グラフにおいて、ランダムウォークに怠惰性を導入することにより被覆時間が多項式時間に抑えら れることが示されている。しかし、我々の知る限り、一般的な環境下において、ランダムウォークの怠惰性が被覆時 間に与える影響はこれまで十分明らかにされていない。そこで本稿では、規模や密度の異なるさまざまな動的グラフ において、ランダムウォークの怠惰性がランダムウォークの被覆時間および初回到着時間に与える影響を明らかにす る。具体的には、7 種類のグラフ生成モデルを用いて、構造・規模・密度の異なるさまざまなグラフを生成し、それら のグラフ中のリンクをレート τでランダムに張り替えることにより、マルコフ動的グラフを人工的に生成した。その マルコフ動的グラフにおける怠惰性を有するランダムウォーク (怠惰ランダムウォーク) の平均被覆時間および初回到着時間を、単純ランダムウォークの平均被覆時間および初回到着時間と比較する。 |
| （英） | Graph exploration with a random walk has a wide range of engineering applications, and its mathematical properties have been actively studied. In recent years, not only random walks on static graphs (topology structure does not change over time), but also random walks on dynamic graphs (topology structure changes over time) have attracted a lot of attention. It has been shown that on an evolving graph (a type of dynamic graphs), the cover time of a random walk can be reduced to polynomial time by introducing laziness to a simple random walk. However, to the best of our knowledge, the effect of random walk laziness on the properties of the cover time of the random walk under a typical environment have not been sufficiently clarified. In this study, we therefore investigate the effect of random walk laziness on the random walk properties for a variety of evolving graphs with different sizes and densities. Specifically, we artificially generate Markov evolving graphs by generating various graphs with different structure, size, and density using seven different graph generation models and randomly rearranging the links in these graphs by rate τ, and we compare the mean cover time and mean first passage time of a lazy random walk on its Markovian dynamic graph with those of a simple random walk. | |
| キーワード | （和） | ランダムウォーク / 怠惰ランダムウォーク / 進展グラフ / 平均初回到着時間 / 平均被覆時間 / / / |
| （英） | Random Walk / Lazy Random Walk / Evolving Graph / Mean First Passage Time / Mean Cover Time / / / | |
| 文献情報 | 信学技報, vol. 122, no. 306, IA2022-57, pp. 50-55, 2022年12月. | |
| 資料番号 | IA2022-57 | |
| 発行日 | 2022-12-05 (IA) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IA2022-57 |
|
| 研究会情報 | |
| 研究会 | IN IA |
| 開催期間 | 2022-12-12 - 2022-12-13 |
| 開催地（和） | 広島大学 東千田キャンパス 未来創生センター |
| 開催地（英） | Higashi-Senda campus, Hiroshima Univ. |
| テーマ（和） | 性能評価とシミュレーション、信頼性技術、スループットやトラヒックの計測、品質(QoS)制御、輻輳制御、トラヒック・フロー制御、オーバーレイネットワーク・P2P、IPv6 、マルチキャスト、ルーティング、DDoS及び一般※※※ 本研究会の2日目は情報指向ネットワーク技術特別研究会(ICN)とも併催です※※※ |
| テーマ（英） | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, IPv6, Multicast, Routing, DDoS, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IA |
| 会議コード | 2022-12-IN-IA |
| 本文の言語 | 日本語 |
| タイトル（和） | 動的グラフにおいてランダムウォークの怠惰性がグラフ探査の効率性に与える影響 |
| サブタイトル（和） | |
| タイトル（英） | On the Impact of Random Walk Laziness on Efficiency of Graph Exploration in Dynamic Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ランダムウォーク / Random Walk |
| キーワード(2)（和/英） | 怠惰ランダムウォーク / Lazy Random Walk |
| キーワード(3)（和/英） | 進展グラフ / Evolving Graph |
| キーワード(4)（和/英） | 平均初回到着時間 / Mean First Passage Time |
| キーワード(5)（和/英） | 平均被覆時間 / Mean Cover Time |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 中川 大輝 / Daiki Nakagawa / ナカガワ ダイキ |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 岩田 丈了 / Takeaki Iwata / イワタ タケアキ |
| 第2著者 所属（和/英） | 関西学院大学大学院 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 松尾 涼太郎 / Ryotaro Matsuo / マツオ リョウタロウ |
| 第3著者 所属（和/英） | 関西学院大学大学院 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 大崎 博之 / Hiroyuki Ohsaki / オオサキ ヒロユキ |
| 第4著者 所属（和/英） | 関西学院大学大学院 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2022-12-13 10:40:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IA |
| 資料番号 | IA2022-57 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | no.306 |
| ページ範囲 | pp.50-55 |
| ページ数 | 6 |
| 発行日 | 2022-12-05 (IA) |
[研究会発表申込システムのトップページに戻る]