Link Prediction in Complex Networks Based on Local and Global Topological Structures

Abstract

Link prediction refers to the problem of predicting the occurrence of a link between two entities. It is a popular research area with important applications in a variety of disciplines. There are many different methods proposed for link prediction; some use local network properties, and others use global properties. The purpose of this research is to explore and utilize link prediction approaches based on perturbation methods, with a focus on combining local and global information to develop a robust and efficient method. To achieve this aim, we have constructed a combination method where we used the structural perturbation method (SPM) as a global method, and for local methods we used some of the well-known local similarity methods. The SPM captures information about the whole network structure, while local methods capture local information about network structure. We focused on understanding the mechanism behind the SPM to further improve the efficiency and accuracy of the prediction algorithms. As such, we were able to reduce the degree of uncertainty that comes with networks, and to boost the mechanism of adding links to predict the missing links. Furthermore, we reduced the amount of eigenvalues used in the perturbation and proved that calculating the perturbation one time instead of taking the average of ten perturbations for each iteration, which was one of the reasons that SPM has a high computational cost, is a sufficient approach and by doing so, we have reduced the computational time of this method. Thus, we have clarified several misconceptions related to the implementation of spectral methods. The assumption that the links appear at random is one of the reasons that the SPM gives good precision results. However, the precision deteriorates if the links do not appear at random. The assumption that the precision of the SPM improves if the similarity indices are obtained from the average of 10 perturbed networks is not necessarily true. The application of the methods presented in this research could be used to model many different applications, such as, in the analysis of social networks, the detection of the underground relationships between terrorists, recommender systems in e-commerce web sites to enhance the sales. In addition, for some networks, especially biological networks such as protein-protein interaction networks, metabolic networks and food webs, the discovery of links or interactions is costly in the laboratory or the field. A highly accurate prediction that we achieved in our results can reduce the experimental costs in these types of networks. It can also be used for the reconstruction of networks and evaluation of network evolving mechanism. The results of this research shows that it is possible to construct a method that is combination of local and global information and produce better predictions than existing methods. In addition, our proposed models have significantly improved the accuracy of the prediction of missing links and reduced the time and complexity associated with the perturbation methods.