A link prediction algorithm based on low-rank matrix completion

摘要

Link prediction is an essential research area in network analysis. Based on the technique of matrix completion, an algorithm for link prediction in networks is proposed. We propose a new model to describe matrix completion. In addition to the observed data, the model takes the noise matrix into account, which is important for detecting missing links. We propose an alternative iteration algorithm to solve matrix completion. The algorithm uses the proximal forward-backward splitting to minimize the nuclear and L2,1 norm simultaneously. A random projected shrinkage operator on the singular values is defined, and an algorithm for implementing the projected shrinkage operator is presented. Using this operator, the time complexity of our algorithm is reduced greatly and reaches the lower bound of the time complexity for a similarity-based link prediction method. The empirical results of real-world networks show that the proposed algorithm can achieve higher quality prediction results than other algorithms.