Research On Link Prediction Algorithm For Complex Networks Based On Similarity

There are a large number of complex systems in the real world.When abstracting them as complex networks for research,the information collection of network structures is not complete.Link prediction mainly uses existing network information to predict potential or missing and spurious connections in the abstract process.Due to the availability of the network structure,the link prediction algorithm based on the similarity of the network structure has become the mainstream algorithm.Among them,the algorithm based on local random walk has higher accuracy,but does not consider the influence of the local aggregation degree of the network on the transition probability between nodes.In addition,multiple different types of networks with the same entities are connected to each other,they can be represented as multi-layer networks.Some single-layer network prediction algorithms are also extended to the study of multi-layer networks,but they do not consider the information between layers.The existing multi-layer network link prediction algorithms do not consider the topology information of the target layer,and the parameters in the calculation method of the inter-layer information are difficult to determine.Therefore,aiming at the problems existing in link prediction algorithms for single-layer networks and multi-layer networks,this paper proposes a similarity-based link prediction algorithm for complex networks.The main research contents of this paper are as follows:For single-layer networks,in order to solve the problem that the link prediction algorithm based on local random walk ignored the influence of the local network structure on the transition probability and was not suitable for the network with high local aggregation degree,single-layer networks link prediction algorithm based on the similarity of superimposed random walk gravity models was proposed.Firstly,the algorithm considered the local information of the network,used the degree of the nodes or combined the clustering coefficient of the nodes and the RA algorithm to improve the transition probability matrix of the random walk.Then,the transition probability matrix was applied to superimposed local random walks to quantify the effect of local network structure on the walk transition.Finally,the gravity model parameters were redefined using the transition probabilities and shortest paths obtained by superimposing local random walks,the similarity between nodes was calculated.Compared with the algorithm based on local information,paths,random walks and clustering coefficients of nodes,in the networks without local high degree of aggregation,the average AUC index of the proposed algorithm was0.951,an average increase of 1.3%,and the average Precision index was improved by 0.9%;in the networks with local high degree of aggregation,the average AUC index of the proposed algorithm was 0.978,an average increase of 5.5%,and the average Precision index was improved by 1.4%.Experimental results show that the proposed algorithm can effectively perform link prediction for single-layer networks.For multi-layer network,in order to solve the problem that the link prediction algorithm of multi-layer network ignored the topology information in the network layer and the calculation of information between layers was difficult to determine,multi-layer networks link prediction algorithm based on grey correlation similarity was proposed.Firstly,the multi-layer network was divided into the target layer and other layers,and the link prediction was performed on the target layer.Considering the influence of the shared and non-shared edges of other layers and the target layer on the target layer,a new inter-layer correlation method was proposed.Then,the algorithm used the single-layer network link prediction algorithm based on the similarity of the superimposed random walk gravity model to quantify the layers of each layer of the network.Finally,the grey relational degree analysis method was used to combine the inter-layer information and the intra-layer information to calculate the similarity between the potential connection nodes in the target layer.Compared with other multi-layer network algorithms,the average AUC index of the proposed algorithm was improved by 8.75%,and the average Precision index was improved by 21.5%.Experimental results show that the proposed algorithm can more effectively predict links in multi-layer networks.