Research Of Link Prediction Algorithm Based On Community Structure And Self-information In Complex Networks

In real world, many systems such as social system, biological system, information system and even the road and the river can be abstractly represented by complex network. Node of it denotes the object and link denotes the interaction between objects. The valuable information behind complex network accumulated with the system changing, and the interaction(or links) as a part of those information, it is quite necessary to get them. As one of the fundamental issues in information mining field, link prediction can reveal those implicit message in networks according to their topological structure and node attributes, and can be an important way for repairing incomplete network as well. By measuring the factors which closely related to the network and taking full advantage of these factors, link prediction is mean to predict the missing links or emerging links in the future in network.With the advent of “big data era”, there are some link prediction algorithms have been unable to meet the needs of practical problems, and accuracy of algorithms need to be improved as well. The mainstream research direction on link prediction is based on node similarity, benefitting to their low computational complexity and high accuracy. The methods based on probabilistic model have also received more attentions than before because of continuously innovative computer technology. The predict accuracy has become higher with the more precise model building, and the computational complexity is gradually reduced simultaneously.This paper made a further study on these two directions under the previous work, then from the perspective of network ‘s structural properties and information theory, this paper proposed the CS-Based algorithm using community structure and the CNSI algorithm using conditional selfinformation. The idea of CS-Based algorithm is inspired by the properties of community structure itself. Nodes in community have closely relationship, and nodes across communities have loosely relationship. We do believe that this phenomenon play an important role in link prediction, the similarity between nodes in community will be reinforced by community tightness itself, and nodes’ similarity across communities will also be reinforced by the tightness between communities. If we embed this feature in link prediction, it will largely promote accuracy of the algorithms. The experiment on real datasets has confirmed CS-Based algorithm is better than other algorithms. For the CNSI algorithm, we build the predictive model through information theory knowledge, turning the nodes’ similarity into the conditional self-information under some important features of network existing. If the more features exist, the less self-information the node pair possesses, and there will be emerging a link with higher probability between that node pair. Then the experiment results has also demonstrated the good prediction performance of CNSI algorithm and it is better than those classical algorithms.