关键词: 链接预测, 低秩估计, 局部约束, 社会网络, 数据挖掘

Abstract: In the big data era, the research on link prediction for social network on the Web and other complex networks has attracted popular interest. Some methods with link prediction have been widely used in social network relationship mining, individual recommendation and biological pharmacy. In the link prediction problem, the similarity matrix is selected for representing the probability of existed links between any nodes. Therefore, the calculation method for estimating the similarity matrix becomes the most crucial step. Recent years, most research focuses on the methods based on data analysis which construct the similarity relationship matrix by data-dependent machine learning and optimization algorithm. This paper proposes a novel data-dependent link prediction method with global low-rank structure assumption and local constraint of node features in the network. The new proposed method is designed for scalable divide-and-conquer calculation for complex network and suitable for distributed computation. Extensive experiments on several real-world datasets show that the proposed link prediction measure obtains competitive performance compared with the baselines. The results also indicate the new algorithm is effective, robust and scalable for complex networks.

Key words: link prediction, low-rank estimation, local constraint, social network, data mining