Link Prediction In Complex Networks Based On Fusion Of Classical Indexes

In recent years,research on complex networks has received extensive attention from researchers of various fields.Among them,link prediction,which aims at predicting unobserved links or links that will appear in the future in complex networks,has also become an important research topic due to its theoretical importance and practical applications.Link prediction is widely applied on biology,computer science,social science,etc.In addition to its practical application value,it also has important theoretical significance on research of complex network.Over the past decades,various link prediction algorithms have been proposed,which can roughly be divided into two categories: similarity-based algorithms and maximum likelihood-based ones.Among them,similarity-based algorithms provide the simplest framework and becomes the mainstream.On the other hand,although the likelihood-based algorithms does not achieve the most competetive performances in terms of prediction accuracy and computational complexity,they can provide some deeper insight on the organization principle of the networks.Generally,there are no single algorithm that can achieve the best performance on all kinds of networks.So as in many other fields such as pattern recognition,it is important to investigate how to combine different kinds of individual methods in link prediction to take advantages from them all.Motivated by this idea,we proposed three new indices/framework by combining different kinds of existing indices/methods.The first one is a new index that combines the Local Path index and the Preferential Attachment index,which can be shown to provide higher prediction accuracy with improved robustness.The second one combines the Structural Perturbation Method and the Resource Allocation index which also exhibited excellent performances in experimental studies.Lastly,we proposes a more general framework which can combine most of the similarity indexes and improve their prediction accuracy by some kind of repeated denoising processes.The major contributions can be summarized as follows:(1)A new link prediction index that combines Preferential Attachment index and Local Path index.It is generally believed that paths of all lengths between two candidate nodes will contribute to the similarity between them,so at least in principle it is helpful to characterize the similarity between nodes by considering them all.While Local Path index discards the information of paths whose length are larger than a certain value.Since all the paths between the two candidate nodes will pass through their neighbors,it is natural to think that the number of paths between them can be roughly characterized by their degrees,whose products are the classical Preferential Attachment index.Although the Preferential Attachment index does not have a high prediction accuracy,it has very strong overall robustness.Based on these observation,we propose a new index by combine these two indices.Experiments on different networks indicate that the new index has better prediction accuracy with improved robustness.(2)A new link predicition index that combines Structural Perturbation Method and the Resource Allocation index.The SPM algorithm uses the reconstructed adjacency matrix after structural perturbation to predict edges.In this paper we think that reconstructed adjacency matrix is closer to actual network and contains more information than the original adjacency matrix.In order to make full use of these information,we further apply the Resource Allocation index to the reconstructed adjacency matrix,and thus obtains a new link prediction index.Experimental studies also indicated that the new index not only has better prediction accuracy,but also performs well in terms of robustness.(3)A new link prediction method based on some kind of repeated denoising processes.There are a lot of noises in the data set of the observed network strucuture.And it has been shown the missing links can be revealed by denoising the observed data sets.In order to reduce the influence of noise,we propose a new kind of denoise process by directly removing those edges with low similarity scores.Then we predict some new links with high similarity scores.After repeating this process several times,we obtain the final prediction result by combining the predict results during these denoising processes.This method provides a general framework which can apply to any similarity index or any combination of them.Experimental studies indicate that it can improve the prediction accuracy effectively compared with the original similarity indices.