Link Prediction In Complex Networks Based On Perturbation Method

Link prediction is an important research topic in the study of complex networks.Generally speaking,it estimates the existence possibility of links between two nodes based on the known information of the network.In recent years,link prediction has attracted extensive attention from researchers in many fields,not only because of its theoretical value,but also because of its important applications.Link prediction can be used to study the evolution of complex networks,and it can be applied to recommender system in practical application.How to accurately and efficiently predict unknown links in the complex network is a very important work.In recent years,a large number of link prediction algorithms have been proposed,among which the node similarity based ones form the mainstream-framework.Although these traditional methods of link prediction achieved some success,they still have many shortcomings.For example,the traditional methods based on common neighbors are highly degenerate,most of the node pairs have the same score and hard to distinguish;secondly,these indices are static and deterministic without considering any dynamic behavior.But the real networks are often dynamically generated,and the process of evolution also affects the formation of links.The methods proposed in this thesis have improved and studied the shortcomings of the traditional methods,they all revolve around the concept of perturbation,which uses part of the known information to restore the structure of the original network and obtain some unknown information,and the main contents are as follows:(1)A new link prediction algorithm based on matrix perturbation and decomposition in undirected networks.By combining two existing methods which are of complementary nature,we propose a new method that can take advantage from both,SPM method can be used to complete the lost information,and the LR decomposition can remove the noise in the network.The results in multiple real undirected networks show that our method has a better performance.Besides,the method also provides a new framework for link prediction: by directly studying the adjacency matrix as a whole,which can make use of the tools from matrix theory.(2)A new link prediction algorithm based on matrix perturbation and decomposition in directed networks.Since SPM can only be applied to undirected networks,the application of the previous algorithm is also limited to undirected ones.However,many real world networks are directed ones.Since it is of great significance to extend our algorithm to directed networks.By decomposing the asymmetric adjacency matrix into symmetric and antisymmetric parts,we use the similar method of last work to perturb and decompose it.The prediction effect of this method is verified on multiple directed networks.(3)Link prediction based on network evolution evaluation.The network of the real world is evolving,so it is better to predict the missing links dynamically during the evolution process.By combining the perturbation method and some similarity indexes to simulate the evolution process of the network,we proposes an evolutionary evaluation algorithm.Moreover,we also propose an improved algorithm based on evolutional likelihood.These two algorithms provide a new framework for link prediction by making use of basic indexes.Experimental results on many real world networks indicate that they perform very well,and it can improve the performance of these basic indices without dramatically increasing the computational cost.