Research Of Link Prediction Algorithm Based On Network Structure And Random Walk Theory

As one of the important problems in the field of network science,link prediction has attracted increasing attention from scholars in recent years.Link prediction is based on the observed network structure and existing node information,and uses the prediction algorithm to calculate the probability of a link between non-adjacent nodes.However,the prediction algorithm based on network structure similarity can not accurately grasp the structural features between the current nodes when mining network structure information,which leads to the low utilization of network structure.In response to this problem,this dissertation conducts link prediction from the perspective of local network structure similarity and global network structure similarity.The main work and conclusions are as follows:1.In undirected and unweighted networks,the traditional prediction algorithms based on local structure of network only focus on local structures of the common neighbors,which neglect the contribution of local topological structures between node pairs and their common neighbors.To solve the problem of local structural different between nodes,a link prediction algorithm based on common neighbors and intimate degree is proposed.From the view of the local network structures of node pairs,this dissertation considers the number of common neighbor nodes and the topological structures between node pairs and common neighbor nodes,respectively.The experimental results show that proposed index outperforms other five local similarity indices.Then,according to characteristic of the similarity index,this algorithm is extended to weighted networks.We improve three weighted prediction algorithms and achieve great results.2.Link prediction based on the random walk theory hold that the general walk-off particles are equally move between nodes.However,it can be seen from the degree correlation of the network that the particles do not completely follow the equal probability,but may be affected by the degree of node.Aiming at the problem that the traveling particles are biased to move in undirected and unweighted networks,a link prediction algorithm of biased random walk with restart is proposed.From the view of the global structure,the algorithm considers the biased transfer of the traveling particles based on nodes' degree value,and proposes a similarity index of biased random walk with restart.Then this index is applied to the link prediction process.The experiment shows that the bias-transferred prediction algorithm is better than the unbiased prediction.And under the optimal bias coefficient,the prediction results are more accurate than other local and global similarity indices.Similarly,in order to expand the applicability of the algorithm,the proposed similarity index is extended to directed networks.It is found that there is still a bias transfer phenomenon in directed networks.Moreover,the link prediction algorithm of biased random walk with restart performs better.