Link Prediction in Directed Network and Its Application in Microblog

Link prediction tries to infer the likelihood of the existence of a link between two nodes in a network. It has important theoretical and practical value. To date, many link prediction algorithms have been proposed. However, most of these studies assumed that links of network are undirected. In this paper, we focus on link prediction in directed networks. We provide an efficient and effective link prediction method, which consists of three steps as follows: (1) we locate the similar nodes of a target node; (2) we identify candidates that the similar nodes link to; and (3) we rank candidates using weighing schemes. We conduct experiments to evaluate the accuracy of our proposed method using real microblog data. The experimental results show that the proposed method is promising. 1. Introduction Many complex systems, such as social, information, and biological systems, can be modeled as networks, where nodes correspond to individuals or agents, and links represent the relations or interactions between two nodes. Network is a useful tool in analyzing a wide range of complex systems. Many efforts have been made to understand the structure, evolution, and function of networks. Recently, the study of link prediction in network has attracted increasing attention. Link prediction tries to infer the likelihood of the existence of a link between two nodes, which has important theoretical and practical value. In theory, research on link prediction can help us understand the mechanism of evolution of complex network. In practical application, link prediction can be applied to many practical fields. For example, link prediction can be used in biological network to infer existence of a link so as to save experimental cost and time. It also can be utilized to online social networks to recommend friends for users, so as to improve the users’ experience. To date, many link prediction algorithms have been proposed. Most of them are designed based on node similarity. The higher the similarity score between two nodes, the higher the possibility of them being connected. In order to measure the node similarity, many link prediction algorithms exploit network structure [1]. One reason is that links in a network indicate certain similarity between the nodes they connect. According to the domain of required structure of network, there are two main kinds of approaches in the domain of link prediction. The first one is based on local features of a network, detecting mainly the local nodes’ structure; the second one is based on global features of a network, focusing on the overall