Research On Network Link Prediction Algorithm Based On The Information Of The Node Pair To Be Predicted

With the Intelligentized reconstruction of society and industry,various forms of complex network models have involved in production and modern life with the development of communication technology.The related research on complex networks has also attracted the attention of scholars in various disciplines.Link prediction is an important branch of complex network research,which predicts the possibility of links between nodes that are not directly connected based on known information in the network.In recent years,research on link prediction has divided into several different research interests.Based on the topology of the network,this thesis analyzes the characteristics and shortcomings of available link prediction algorithms from two aspects that the overall topology and local path structure of the network,and proposes new link prediction algorithms from these two aspects.This research mainly focuses on the following two aspects:(1)It is analyzed that the relationship between the similarity of overall network information and the nodes to be tested.Two link prediction algorithms based on the information of nodes to be tested and the scale-free property are proposed by comparing the advantages and disadvantages of resource allocation algorithms and preferential attachment algorithms.One is the resource allocation under the scale-free effect of the node pair to be tested(RSF),and the other is the Resource allocation under the weak scale-free effect of the node pair to be tested(RSW).Link prediction experiments are conducted on 14 real networks to verify the good predictive performance of the proposed algorithms.In nine networks,RSF is better than basic algorithms such as resource allocation algorithms or preference connection algorithms.As compared to other algorithm,the prediction accuracy of each network has improved by a minimum of 0.4% and a maximum of 4.6%.The algorithm that based on the weak scale-free property of the network has outstanding prediction performance in three networks with relatively uniform degree distribution,with improvements of 3.3%,12.8%,and 29.8% compared to the basic algorithm,respectively.In addition,the influence of the scale-free property of the network on the algorithm’s performance is analyzed,and the applicable network types of the algorithms are pointed out.The robustness experiments of the algorithms further verify their reliability and the important relationship between the scale-free property of the network and the algorithm’s performance.(2)According to the impact of local path structure between node pairs to be tested on similarity,four link prediction algorithms that based on second-order and third-order paths between node pairs to be tested are proposed.The similarities and differences of the second-order and third-order path topologies between node pairs are analyzed,and it is pointed out that the similarity of node pairs is affected differently by paths of different lengths.Therefore,based on the second-order forms of resource allocation algorithms and local community algorithms,four link prediction algorithms based on the combination of the second-order path and the third-order path between node pairs to be tested are proposed.Through link prediction experiments in 15 real networks,it is verified that the performance of the algorithm combining second-order and third-order paths is better than that of the algorithm using a single path.And the prediction performance of the algorithm based on second-order local community paradigm and third-order resource allocation is the most prominent than other three algorithms,outperforming the resource allocation algorithm in eight networks,with a minimum prediction performance improvement of 0.7% and a maximum improvement of 14%.Also in robustness experiments,it is verified that the proposed algorithm has good prediction performance and robustness.