| 講演名 | 2023-03-03 グラフ更新時のインデックス再生成を排したTop-k Personalized PageRank演算 山下 剛志(慶大), 松本 直己(慶大), 金子 晋丈(慶大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 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 |
| 資料番号 | IN2022-117 |
| 発行日 | 2023-02-23 (IN) |
| 研究会情報 | |
| 研究会 | IN / NS |
|---|---|
| 開催期間 | 2023/3/2(から2日開催) |
| 開催地（和） | 沖縄コンベンションセンター + オンライン開催 |
| 開催地（英） | Okinawa Convention Centre + Online |
| テーマ（和） | 一般 |
| テーマ（英） | General |
| 委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) / 大石 哲矢(NTT) |
| 委員長氏名（英） | Kunio Hato(Internet Multifeed) / Tetsuya Oishi(NTT) |
| 副委員長氏名（和） | 村瀬 勉(名大) / 三好 匠(芝浦工大) |
| 副委員長氏名（英） | Tsutomu Murase(Nagoya Univ.) / Takumi Miyoshi(Shibaura Insti of Tech.) |
| 幹事氏名（和） | 城 哲(KDDI総合研究所) / 渡部 康平(長岡技科大) / 秦泉寺 久美(NTT) / 濱田 浩気(NTT) / 池邉 隆(NTT) / 山口 実靖(工学院大) |
| 幹事氏名（英） | Tetsu Jyo(KDDI Research) / Kouhei Watabei(Nagaoka Univ. of Tech.) / Kumi Jinzenji(NTT) / Koki Hamada(NTT) / Takashi Ikebe(NTT) / Saneyasu Yamaguchi(Kogakuin Univ.) |
| 幹事補佐氏名（和） | / 三原 孝太郎(NTT) |
| 幹事補佐氏名（英） | / Kotaro Mihara(NTT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Network Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフ更新時のインデックス再生成を排した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 |
| 第 1 著者 氏名（和/英） | 山下 剛志 / Tsuyoshi Yamashita |
| 第 1 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 第 2 著者 氏名（和/英） | 松本 直己 / Naoki Matsumoto |
| 第 2 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 第 3 著者 氏名（和/英） | 金子 晋丈 / Kunitake Kaneko |
| 第 3 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 発表年月日 | 2023-03-03 |
| 資料番号 | IN2022-117 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | IN-407 |
| ページ範囲 | pp.305-310(IN), |
| ページ数 | 6 |
| 発行日 | 2023-02-23 (IN) |