| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2023-03-03 14:30 グラフ更新時のインデックス再生成を排したTop-k Personalized PageRank演算 ○山下剛志・松本直己・金子晋丈（慶大）  IN2022-117 |
|
| 抄録 | （和） | Top-k Personalized PageRank (PPR) は起点ノードに対して重要なkノードを決定するグラフ解析手法である．Top-k PPR 演算では，各ノードに対するインデックスを事前に生成し，演算時に使用することで高速な演算が可能になる.しかし，動的グラフにおいて演算精度を保証するためには，グラフ更新のたびに一部のノードにおいてインデックスを再生成する必要があり，その演算コストが課題であった.そこで本稿では，演算精度を保証しないものの実用的に十分な演算精度を達成できる手法を提案した.具体的には，インデックスが参照されやすいノードほどグラフ更新前後でインデックスが変化しにくいことに注目した上で，グラフ更新時のインデックス再生成を完全に排し，演算時に過去のグラフで生成したインデックスをそのまま使用する手法を提案した.実世界のグラフを用いて，提案手法の演算精度を評価した結果，インデックス生成時からグラフのエッジ数が2倍になるまでグラフが成長したとしても，Top-128 PPR の演算精度は最大 0.1% 程度しか低下しないことが明らかになった. |
| （英） | Top-k Personalized PageRank (PPR) is graph analysis method to determine k important nodes with respect to a source node. To realize fast Top-k PPR computations, indexing for each node and using them during computations is effective. However, to ensure accuracy on dynamic graphs, re-indexing at part of nodes is required for every graph update, and the computation is costly. In this research, we proposed a method which don't ensure accuracy, but achieves sufficient accuracy for practical use. Specifically, focusing on the fact that indexes that are more easily referred to during computations are less likely to change by graph updates, we proposed a method that completely eliminates re-indexing for graph updates. Evaluation of the proposed method with real-world graph dataset shows that accuracy of Top-128 PPR decreases by only up to 0.1% comparing to existing accuracy ensuring method, even when the number of edges double. | |
| キーワード | （和） | 動的グラフ / Personalized PageRank / インデックス / ランダムウォーク / / / / |
| （英） | Dynamic Graphs / Personalized PageRank / Index / Random Walks / / / / | |
| 文献情報 | 信学技報, vol. 122, no. 407, IN2022-117, pp. 305-310, 2023年3月. | |
| 資料番号 | IN2022-117 | |
| 発行日 | 2023-02-23 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2022-117 |
|
| 研究会情報 | |
| 研究会 | IN NS |
| 開催期間 | 2023-03-02 - 2023-03-03 |
| 開催地（和） | 沖縄コンベンションセンター + オンライン開催 |
| 開催地（英） | Okinawa Convention Centre + Online |
| テーマ（和） | 一般 |
| テーマ（英） | General |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2023-03-IN-NS |
| 本文の言語 | 日本語 |
| タイトル（和） | グラフ更新時のインデックス再生成を排したTop-k Personalized PageRank演算 |
| サブタイトル（和） | |
| タイトル（英） | Top-k Personalized PageRank Computation without Re-indexing for Graph Updates |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 動的グラフ / Dynamic Graphs |
| キーワード(2)（和/英） | Personalized PageRank / Personalized PageRank |
| キーワード(3)（和/英） | インデックス / Index |
| キーワード(4)（和/英） | ランダムウォーク / Random Walks |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / ヤマシタ ツヨシ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 松本 直己 / Naoki Matsumoto / マツモト ナオキ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第3著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2023-03-03 14:30:00 |
| 発表時間 | 20分 |
| 申込先研究会 | IN |
| 資料番号 | IN2022-117 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | no.407 |
| ページ範囲 | pp.305-310 |
| ページ数 | 6 |
| 発行日 | 2023-02-23 (IN) |
[研究会発表申込システムのトップページに戻る]