精度保証付きPersonalized PageRankの高速化

藤原 靖宏   真  山室 健  塩川 浩昭  鬼塚 真  
(データ工学研究専門委員会推薦論文)

誌名
電子情報通信学会論文誌 D   Vol.J97-D   No.4   pp.738-751
発行日: 2014/04/01
Online ISSN: 1881-0225
論文種別: 特集論文 (データ工学と情報マネジメント論文特集)
専門分野: グラフマイニング
キーワード: 
Personalized PageRank,  関連度計算,  高速,  アルゴリズム,  

本文: PDF(881.8KB)
>>論文を購入


あらまし: 
Personalize PageRank (PPR)はグラフマイニングにおいて有用な関連度の計算方法として知られている.本論文ではPPRに対して(1)特定のノードの関連度と,(2)上位K個のノードと(3)関連度がしきい値より大きいのノードを計算の精度を保証し,すなわち理論的に計算結果を犠牲にすることなく正確に高速計算することを対象とする.オリジナルのPPRの手法は問い合わせ分布に対する関連度を全てのノードに対して収束するまで繰り返し計算によって求める.この手法の問題点として特定のノードや関連度の高いノードのみの関連度を計算できないということがあげられる.提案手法は特定のノードの関連度を疎行列を用いて計算し,関連度の高いノードを関連度の下限値と上限値を用いて求める.実験により提案手法は既存手法より大幅に高速化を達成できることを確認した.