講演抄録/キーワード |
講演名 |
2021-12-17 12:40
[ショートペーパー]グラフ上の不可逆ランダムウォークの初回到着時間および被覆時間に関する一検討 ○河岸哲哉・萩倉 丈・松尾涼太郎・大崎博之(関西学院大) IA2021-41 |
抄録 |
(和) |
近年、グラフ上のランダムウォークの数理的な特性が明らかにされつつあり、不可逆ランダムウォークや、自己回避型ランダムウォーク、分岐型ランダムウォークなど、単純ランダムウォークの派生モデルの研究も活発に行われている。
不可逆ランダムウォークは、単純ランダムウォークに、直前に訪問したノードへの再訪を禁止するという単純な機構を持たせたものである。不可逆ランダムウォークは、単純ランダムウォークよりも良好な特性を持つことが知られている。
しかし、グラフ構造が不可逆ランダムウォークの特性に与える影響はこれまで十分に明らかにされていない。
そこで本稿では、2 種類の特性の異なるグラフ (ランダム正則グラフおよびコンフィギュレーションモデルによって生成されたグラフ) 上での不可逆ランダムウォークの平均初回到着時間、およびランダム正則グラフ上での不可逆ランダムウォークの平均被覆時間を導出する。さらにいくつかの数値例により、グラフ構造が不可逆ランダムウォークの平均初回到着時間および平均被覆時間に与える影響を分析する。 |
(英) |
Recently, mathematical properties of random walks on a graph have been studied.
Also, several extended models of a simple random walk, such as the non-backtracking random walk, the self-avoiding random walk, and the branching random walk, have been actively studied. The non-backtracking random walk is a simple random walk with a simple mechanism of prohibiting revisits to nodes that have been visited immediately before.
The non-backtracking random walk is known to have better properties than a simple random walk.
However, the effect of graph structure on the properties of the non-backtracking random has not been clarified well.
In this paper, we derive the mean first passage time of the non-backtracking random walk on two types of graphs (i.e., random regular graphs and graphs generated by the configuration model) and the mean cover time of the non-backtracking random walk on random regular graphs.
Furthermore, we analyze the impact of the graph structure on the mean first passage time and the mean cover time of the non-backtracking random walk by several numerical examples. |
キーワード |
(和) |
ランダムウォーク / 平均初回到着時間 / 平均被覆時間 / 不可逆ランダムウォーク / ランダム正則グラフ / コンフィギュレーションモデル / / |
(英) |
Random Walk / Mean First Passage Time / Mean Cover Time / Non-backtracking random walk / Random Regular Graph / Configuration Model / / |
文献情報 |
信学技報, vol. 121, no. 300, IA2021-41, pp. 56-59, 2021年12月. |
資料番号 |
IA2021-41 |
発行日 |
2021-12-09 (IA) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IA2021-41 |
研究会情報 |
研究会 |
IN IA |
開催期間 |
2021-12-16 - 2021-12-17 |
開催地(和) |
広島大学東千田キャンパス |
開催地(英) |
Higashi-Senda campus, Hiroshima Univ. |
テーマ(和) |
性能評価とシミュレーション、信頼性技術、スループットやトラヒックの計測、品質(QoS)制御、輻輳制御、トラヒック・フロー制御、オーバーレイネットワーク・P2P、IPv6 、マルチキャスト、ルーティング、DDoS及び一般 br>※※※ 本研究会の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 |
会議コード |
2021-12-IN-IA |
本文の言語 |
日本語 |
タイトル(和) |
グラフ上の不可逆ランダムウォークの初回到着時間および被覆時間に関する一検討 |
サブタイトル(和) |
|
タイトル(英) |
A Study on First Passage Time and Cover Time of Non-backtracking Random Walk on a Graph |
サブタイトル(英) |
|
キーワード(1)(和/英) |
ランダムウォーク / Random Walk |
キーワード(2)(和/英) |
平均初回到着時間 / Mean First Passage Time |
キーワード(3)(和/英) |
平均被覆時間 / Mean Cover Time |
キーワード(4)(和/英) |
不可逆ランダムウォーク / Non-backtracking random walk |
キーワード(5)(和/英) |
ランダム正則グラフ / Random Regular Graph |
キーワード(6)(和/英) |
コンフィギュレーションモデル / Configuration Model |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
河岸 哲哉 / Tetsuya Kawagishi / カワギシ テツヤ |
第1著者 所属(和/英) |
関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.) |
第2著者 氏名(和/英/ヨミ) |
萩倉 丈 / Jo Hagikura / ハギクラ ジョウ |
第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.) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2021-12-17 12:40:00 |
発表時間 |
15分 |
申込先研究会 |
IA |
資料番号 |
IA2021-41 |
巻番号(vol) |
vol.121 |
号番号(no) |
no.300 |
ページ範囲 |
pp.56-59 |
ページ数 |
4 |
発行日 |
2021-12-09 (IA) |
|