非負値行列分解を用いた時系列リンク予測

IPSJ Open Access

Bibliographic Information

Other Title
  • Temporal Link Prediction by Non-negative Matrix Factorization

Search this article

Abstract

ソーシャルネットワークやWebページの遷移などに見られるように，多くのデータがグラフ構造として表されており，様々なデータマイニングタスクに対してグラフ構造を利用した手法が研究されている．本論文では，時間的に変化するグラフ構造のリンクを予測する問題を対象とする．従来手法では，時間的順序を持つ複数のグラフを単一のグラフに統合しリンク予測を行う手法や，2次元の行列で表されるグラフを時間方向に拡張した3次元テンソルに対してテンソル分解を行いリンクを予測する手法が研究されてきたが，時間方向の連続的な変化をとらえることが難しいため予測精度が高くないという問題があった．提案手法では，時間的順序を持つ複数のグラフに対して非負値行列分解を用いて対象データの特徴を低次元に集約し，Holt-Winters予測を用いて季節変動やトレンドなどの周期的な変化をとらえた予測を行う．実データを用いて比較実験を行い，提案手法は従来手法より高い性能を示すことを確認した．

As seen in the social networks and web pages, many data are expressed in graph structures and many researches for graphs have been conducted for various data mining tasks. In this article, we focus on the temporal link prediction problem for bipartite graphs. The typical techniques for the problem predict temporal links by either merging a temporal graph sequence into a single static graph or by applying tensor factorization after transforming the temporal graph sequence into a single tensor with additional temporal axis. However, the prediction accuracy for those techniques is not high because they have a difficulty in capturing continuous changes in the time axis. We design an algorithm that combines non-negative matrix factorization and Holt-Winters in order to extract latent features from bipartite graphs and to predict periodic changes in future. We conduct experiments using a real data set and demonstrate that our algorithm achieves higher performance over existing techniques.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top