Link Prediction In Complex Networks Based On Transferring Similarity

Complex networks is an effective tool to study complex systems. Complex systems in the real world are varying with time, so do the corresponding networks. To characterize the change on the network, prediction of the edges changing with time is needed. According to whether the edge changes with time, the networks can be divided into static and dynamic networks and thus the prediction methods are different. In static networks link prediction, existing edges will not change in the next short period of time, and not existing edge may appear in the future. Link prediction theory is of great value in both practical application and theoretical study.Currently, a variety of methods are available. According to the main idea, these methods can be divided into three categories, respectively based on topology structure, Markov chain theory and likelihood theory. The most simple and quick among them are Common Neighbor and Resource Allocation. Such method uses only the most nearest neighboring topology information, limiting the accuracy of the prediction. Based on the thought of transferring similarity, we proposed a novel method named Transferring Similarity based on Resource Allocation by integrating transferring similarity and resource allocation. We also proposed Transferring Structure Similarity based on Resource Allocation method and Multi-step Transferring Similarity based on Resource Allocation method to overcome disadvantages of Transferring Similarity based on Resource Allocation method. In consideration of the contribution of the intermediate nodes to similarity, as compared to resource allocation method, the novel methods more fully utilize intermediate structure information on the path of two nodes. The novel methods improve prediction accuracy while maintaining low time cost.In this paper, the characteristics of these three methods were studied experimentally on the most commonly used data in link prediction field, and comparative analysis is also made between Resource Allocation and novel methods. Experimental results show that the novel method to some certain extent, improve the performance. Transferring Structure Similarity based on Resource Allocation method improves the AUC value of about 0.06 on Power and Router datasets and 0.03 on Yeast and Celegans datasets.Transferring Similarity based on Resource Allocation method improves the AUC value of about 0.06 on Power dataset and little on other datasets. Multi-step Transferring Similarity based on Resource Allocation method improves the AUC value of about 0.06 mainly on Power and Router datasets.