Research On Link Prediction Of Complex Networks Based On Path Similarity

Due to the booming development of Internet technology,human society has entered into the era of complex networks.Link prediction,as one of the important research directions in the field of complex networks,has also been paid more attention by the majority of researchers.Link prediction is a method that uses the observed network information to predict the probability of establishing a link between two nodes in a network that are not yet connected.Link prediction is valuable not only for theoretical studies such as network reconstruction and evolutionary mechanisms,but also has many practical applications as a guide for biological experiments,recommender systems,and network repair.Finding out the factors that contribute to link prediction has always been an important research direction for the majority of complex network researchers.Similarity-based link prediction algorithms have received widespread attention due to their low complexity.Most current similarity-based link prediction algorithms study the factors of local paths between common neighbors and connected target node pairs,but they ignore the factor information of paths between nodes and their neighbors.Therefore,in this dissertation,we first assume that the paths between nodes and their neighbors provide the basic similarity characteristics.Then,this dissertation proposes a so-called link prediction method based on the path information between neighbors and node pairs,i.e.,the link prediction algorithm combining second-order neighbor and node-to-path information(SNNPI),which uses the path feature information between node pairs and the path feature information between nodes and neighbors for the similarity calculation of link prediction,and uses the mixed degree value instead of the degree value in the path feature information between node pairs to enhance the prediction effect.Experimental results on eight different real networks show that the SNNPI algorithm has an average lead of 0.94%-9.48% and an overall average lead of 3.5%,and the SNNPI algorithm can obtain higher prediction accuracy than the traditional local similarity-based link prediction methods in most cases.Secondly,this dissertation extends the path feature information from second-order path to third-order path,and further proposes a link prediction algorithm based on multi-order neighbor and node-to-path information(A link prediction algorithm based on multi-order neighbor and node-to-path information(MNNPI),this algorithm further incorporates third-order path feature information based on the original second-order path feature information,in addition,after a series of validation,this dissertation solves the problem of determining parameters in the MNNPI algorithm.The experimental results on the subsequent real networks show that the MNNPI algorithm can make the prediction accuracy further improved,and the prediction accuracy(AUC evaluation index)can be stabilized at a high accuracy(above 0.91)in all the tested real networks.It shows that the link prediction method considering the path similarity between nodes and neighbors and between node pairs is reasonable and feasible.