Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization

We study temporal link prediction problem, where, given past interactions, our goal is to predict new interactions. We propose a dynamic link prediction method based on non-negative matrix factorization. This method assumes that interactions are more likely between users that are similar to each other in the latent space representation. We pro-pose a global optimization algorithm to effectively learn the temporal latent space with quadratic convergence rate and bounded error. In addition, we propose two alternative al-gorithms with local and incremental updates, which provide much better scalability without deteriorating prediction ac-curacy. We evaluate our model on a number of real-world dynamic networks and demonstrate that our model signif-icantly outperforms existing approaches for temporal link prediction in terms of both scalability and predictive power. 1