| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2022-03-11 14:20 動的分散グラフにおける起点近傍の更新のみに注目したランダムウォーク経路合成手法 ○山下剛志・金子晋丈（慶大）  IN2021-48 |
|
| 抄録 | （和） | 多数のランダムウォーク(RW)を用いたグラフ演算では一部の長距離RWがボトルネックとなるため，RWの事前実行が必要となる．しかし，グラフ更新が発生する環境で更新前のグラフで事前実行した結果を用いると，演算精度が低下することが問題となる． 本研究では，RWの中盤以降に訪問するノードにおけるグラフ更新と比べて，序盤に訪問するノードにおけるグラフ更新はグラフ演算結果に大きな影響を与えることに注目して，序盤の経路のみを更新後のグラフで生成し，中盤以降は更新前のグラフで生成した経路を連結し，RW経路を合成する手法を提案する．この手法により，演算のボトルネックとなる長距離RWと演算精度の低下を同時に回避しながらRW経路を合成することが可能となる． 実世界のWebグラフを用いて評価した結果，全体の 28 – 56% の RW しか完了していなくても十分な演算精度を達成できることが明らかになった． |
| （英） | In graph calculations with a lot of random walks (RWs), some long RWs become bottlenecks, and thus pre-execution of RWs is required. However, in dynamic graphs, using pre-execution results on the graphs before updates causes a decrease in accuracy. In this research, we focus on the fact that updates of nodes visited in the early stage of RWs have a larger impact on the calculation results than updates of nodes visited in the middle or later stages of RWs. Then, we propose a method to generate RW paths by connecting paths generated in the graph after updates with paths pre-executed in the graph before updates. This method enables to avoid long RWs and decrease in accuracy simultaneously. Evaluation using real-world Web-graphs shows that proposed method can achieve sufficient calculation accuracy even when only 28 - 56 % of RWs are completed. |
|
| キーワード | （和） | ランダムウォーク / 動的グラフ / 分散グラフ / Personalized PageRank / / / / |
| （英） | Random Walks / Dynamic Graphs / Distributed Graphs / Personalized PageRank / / / / | |
| 文献情報 | 信学技報, vol. 121, no. 434, IN2021-48, pp. 103-108, 2022年3月. | |
| 資料番号 | IN2021-48 | |
| 発行日 | 2022-03-03 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2021-48 |
|
| 研究会情報 | |
| 研究会 | NS IN |
| 開催期間 | 2022-03-10 - 2022-03-11 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 一般 |
| テーマ（英） | General |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2022-03-NS-IN |
| 本文の言語 | 日本語 |
| タイトル（和） | 動的分散グラフにおける起点近傍の更新のみに注目したランダムウォーク経路合成手法 |
| サブタイトル（和） | |
| タイトル（英） | A Method for Generating Random Walk Paths Focusing Only on Updates Near A Source Node in Dynamic Distributed Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ランダムウォーク / Random Walks |
| キーワード(2)（和/英） | 動的グラフ / Dynamic Graphs |
| キーワード(3)（和/英） | 分散グラフ / Distributed Graphs |
| キーワード(4)（和/英） | Personalized PageRank / Personalized PageRank |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / ヤマシタ ツヨシ |
| 第1著者 所属（和/英） | 慶應義塾大学大学院 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2022-03-11 14:20:00 |
| 発表時間 | 20分 |
| 申込先研究会 | IN |
| 資料番号 | IN2021-48 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.434 |
| ページ範囲 | pp.103-108 |
| ページ数 | 6 |
| 発行日 | 2022-03-03 (IN) |
[研究会発表申込システムのトップページに戻る]