Link Prediction Algorithm Based On Path Information And Random Walk Theory

Link prediction,an emerging research hotspot in recent years,deals with the restoration and prediction of missing information.And it plays an important role in analyzing network structure and function of complex networks.In order to mine network structure information effectively and reveal the evolution rules of network,researchers have done a lot of research on the prediction algorithms based on the characteristics of network structure.However,due to the particularity of real networks,the algorithms based on the similarity of network structure will face two major problems: inaccurate selection of path structure information and insufficient mining of network information.For the two problems,the dissertation makes the following contributions in the field of link prediction from the aspects of local path structure information and random walk on the global network:(1)Aiming at the characteristics of optimal path to transmit information,a link prediction algorithm based on optimal path similarity is proposed.According to the discriminative features of optimal path,the tight centrality between nodes is defined,which depict influence of optimal path between nodes on information transmission capability.Then,the number of optimal paths and centrality are used to construct the similarity transfer matrix,which integrate the local information and global attributes between nodes to evaluate the similarity between nodes.The results show that the proposed algorithm outperforms other eight similarity indices.The algorithm is more stable.(2)Drawing on the difference of information coupling of topology of different paths between nodes,this thesis proposes a novel similarity algorithm based on local paths weighting.Generally,the current link prediction models based on path information only focus on the contribution of the length and total number of paths between nodes,which ignore the problem of path heterogeneity contribution for paths with equal length with different structures.In order to solve this problem,a local weighted path model is constructed from the perspective of topological information coupling promoting network evolution.This method transforms the abstract edge topology relationship into a explicit mathematical expression.Then,in order to quantify the path weight between nodes,we consider the information coupling degree of topology of links.Then we set the path attenuation parameters to further solve the problem of path heterogeneity contribution.Finally,through the prediction of six real network edges,the results show that the proposed algorithm has higher prediction accuracy and fine robustness.(3)For the unbiased transfer problem of random walks,a global algorithm based on lowest-degree preference random walks with restart is proposed.Based on the application of random walks in link prediction,a preference transfer function is introduced for networks structure,which changes the rule of updation of transition matrix of the original random walk,and solves the problem of equally move of walk-off particles between nodes.And the effect of the preference transition strategy on the convergence of the similarity function is proved.The experimental results show the proposed algorithm can effectively improve the link prediction performance,which proves the algorithm captures more network topology information to a certain extent.