文献

J-GLOBAL ID：202002279914945357   整理番号：20A1867995

保証付き動的グラフ上の再スタートによる高速かつ正確な酔歩【JST・京大機械翻訳】

Fast and Accurate Random Walk with Restart on Dynamic Graphs with Guarantees

著者 (3件)： Yoon Minji (Seoul National University, Seoul, Rebublic of Korea) ,  Jin Woojeong (Seoul National University, Seoul, Rebublic of Korea) ,  Kang U. (Seoul National University, Seoul, Rebublic of Korea)
資料名： ACM Proceedings  (ACM Proceedings)
号： WWW ’18  ページ： 409-418  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 時間発展グラフを与えて,収束と誤差に関する理論的保証によって,高速で正確な方法でノード間の類似性を追跡することができる。再起動(RWR)によるランダムウォークは,ノード間の類似性を推定するための一般的な測度であり,多数のアプリケーションで利用されてきた。多くの実世界グラフは,エッジの頻繁な挿入/欠失で動的である。したがって,効率的方法における動的グラフに関するRWRスコアを追跡することは,データマイニング研究者の間で多くの興味を喚起した。最近,与えられたグラフにわたるスコアの伝搬に基づく動的RWRモデルを提案し,RWRを動的に計算するための以前の他のアプローチを凌駕した。しかし,これらのモデルは,一般化形式でRWRを更新するための厳密性と収束時間を保証することができない。本論文では,有向/無向グラフにおけるノード/エッジの挿入/削除による動的RWRを計算するための高速で正確なアルゴリズムであるOSPを提案した。グラフが更新されたとき,OSPは最初に修正エッジ周辺のオフセットスコアを計算し,更新されたグラフを横断するオフセットスコアを伝播し,次に,更新されたRWRスコアを得るために現在のRWRスコアとそれらを併合する。OSPの厳密性を証明し,OSP-Tを導入し,誤差耐性を用いて精度と計算時間のトレードオフを制御するOSPのバージョンである。再開確率cを与えられた場合,OSP-TはO(log(∋/2)/log(1-c))反復におけるO(∋/c)誤差でRWRスコアを返すことを保証する。広範な実験を通して,OSPは動的グラフ上で既存の静的RWR法よりも4605x速くRWRを追跡し,OSP-Tは,他の最先端の動的RWR法よりも730x低いL1ノルム誤差と3.3x低いランク誤差で15x未満の時間を必要とすることを示した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  測度 ,  無向グラフ ,  応用プログラム ,  *酔歩 ,  類似性 ,  時間発展 ,  データマイニング
準シソーラス用語： オンラインアルゴリズム ,  L1ノルム ,  再起動 , 【Automatic Indexing@JST】

著者キーワード (3件)： オンラインアルゴリズム ,  再スタートを伴う酔歩 ,  時間発展グラフ

分類 (2件)： グラフ理論基礎  (IA02020S) ,  システム・制御理論一般  (IA02010H)

タイトルに関連する用語 (4件)： 保証 ,  グラフ ,  スタート ,  酔歩