Link predicting method based on local effective path degree

Abstract

The invention discloses a link predicting method based on local effective path degree. The method comprises the following steps: step one, building a network model; step two, optionally choosing two unconnected nodes in the network as seed nodes and recording local path degree of each path with the length of 2 between the two seed nodes; step three, calculating the local path degree of each path with the length of 3 between the two seed nodes; step four, calculating local effective path degree similarity indexes of the two seed nodes; step five, repeatedly performing steps 2-4 on all unconnected node pairs and calculating the corresponding local effective path degree similarity index values; and step six, ranking the similarity index values of all the unconnected nodes from high to low, determining that higher values leads to higher possibility of edge connection between corresponding node pairs and taking the node pairs corresponding to former E index values as predicted connection edges. According to the link predicting method based on local effective path degree, the influence of degree distribution and edge connection strength in local paths on the link prediction is considered; the utilization ratio of information is high; the prediction effect is excellent.

Description

technical field [0001] The invention relates to the fields of network science and link prediction, in particular to a link prediction method based on local effective path degree. Background technique [0002] People use complex networks to study the internal laws of real systems and obtain solutions to practical problems. Link prediction is one of the important research topics in complex networks. The link prediction method can use the link prediction algorithm for any node pair that does not have a link on the basis of the existing network structure information. The possibility of generating links during the evolution of the network. [0003] At present, the existing link prediction methods are: based on Markov chain, based on machine learning and based on network topology, etc. Among them, the link prediction method based on network topology has attracted the attention of many researchers. Structural methods can be divided into three categories: similarity-based link pre...

AI Technical Summary

Problems solved by technology

[0004] Among these various similarity-based link prediction methods, most methods do not consider common neighbors for link prediction from the perspective of a first-order path between two unconnected nodes (the path length between two points is 2). The influence is to consider the impact of all paths between two nodes and the nodes on the path on the link prediction results. There are relatively few compromise methods between them. In fact, although high-order paths contain a large amount of network structure information, they must be To some extent, it is beneficial to improve the effect of link prediction, but it does not consider that the higher-order path is better for link prediction.

For example, the LP index proposed by Lu Linyuan and Zhou Tao considers both the second-order path and the third-order path. The effect of link prediction is better than the CN, AA, and RA indexes that only consider the second-order path. The katz index of all paths in the network and other mainstream indicators, it is found that the prediction effect of katz in some networks is not better than that of CN, AA and RA algorithms. At the same time, in the paper of Zhu Xuzhen et al., we can also see that when considering When the length of the path is greater than 3, the AUC index for evaluating the link prediction accuracy shows a decreasing trend. When we compare the LHN-II algorithm with several other classic algorithms, we can also find that this algorithm that considers all paths between nodes In some networks, the effect is not as good as the classic CN, AA and RA indicators

Images