Link Prediction In Complex Networks Based On Information-theoretic Model

Many real world systems can be described by complex networks.The research of complex networks become significant and meaningful.Link prediction aims at estimating the likelihood of the existence of a link based on available edges and the attributes of nodes of the networks.As an important research trend of complex networks,link prediction has attracted increasing attention from researchers in many scientific fields due to its practical and theoretical significance.Generally there are two applications for link prediction,the exploration of existing but undetected links,and the prediction of those links that have not existed before but will appear in the future.Over the past decades,many kinds of link prediction algorithms have been put forward.The simplest framework among these methods is the set of similarity-based methods in which each node pair is assigned a similarity score to estimate the likelihood of the existence of a link.However,a challenge is how to make full use of the various available features simultaneously.In these respect,information theory has been proposed to be a useful tool.This paper aims at designing information-theoretic based link prediction algorithms which provide an effective framework to make good use of multiple available features of a network.First,we extended the existing information-theoretic model to a general information-theoretic model,and designed a novel similarity based index: Neighbor Set Information Allocation Index.Then,we propose a fusion algorithm by combining the new index and the community detection of the networks.At last,we find that the introduction of the perturbation to the networks can provide an efficient way to measure the contribution of any available feature,thus the perturbation based information-theoretic model for link prediction is designed,which reduces computational cost of the algorithm and improves its performance.The main work of this paper as follows:(1)A general information-theoretic model for link prediction.In this part,we have discriminated the contributions of different feature variables even if they belong to the same feature set,and extent the original information-theoretic model to a more general one.Then,a new index based on virtual information allocation process has been proposed:Neighbor Set Information Allocation Index.Experimental results on lots of real networks indicate that the new index has an improved performance.(2)A fusion algorithm for community detection and the Neighbor Set Information Allocation Index.Community structure can be found in most networks,detecting and utilizing the community structure of the networks effectively can increase the prediction accuracy of link prediction algorithms.In this section,by combining the community relevance which represents the relationship between two communities,with the Neighbor Set Information Allocation Index,we proposed a fusion method for link prediction.Many experiments have been carried out to verify for verifying the performance of the new method.(3)Link prediction algorithm based on perturbation.In this method,the relative contributions of different features are determined by disturbing the networks structure and then evaluating their influences.The effect of the networks structure is considered to contribute the prediction accuracy to link prediction.Compared to the local research strategy in information-theoretic based methods,the new method has both lower computational complexity and higher prediction accuracy.Experiments on the real-word networks have been carried out to test the performance of the new method.