Research On Link Prediction In Multi-Relational Networks

With the development of the social of science and technology, and the progress of network and information technology, the link prediction problem for complex networks has become one of the important research areas in the fields of computer science, social science and complex system. In nature, a large number of various systems could be described by complex networks, such as neural networks, electricity power networks, aviation networks and users-commodity network. Link prediction uses the known topological structure of the network to predict the missing and future possible links. In the social network, link prediction can find the potential connection between individuals, reveal users’ potential friends, and recommend products to customers in e-commerce.In the real world, most networks may contain a variety of relationships between individuals. However, the current link prediction research in complex network focuses on a single relationship networks. In addition to the topology structure of the network, the influence and relevance between different types of relationships can also influence the possibility of the link existence. And the traditional link prediction methods usually focus on one type of relation in the network or handle all different types of relations as the same type. Both of these approaches represent a loss of important information. Based on the characteristics of the multi-relational networks, we combine topology structure and similarity between different types of relations to design more accurate and efficient link prediction algorithm. In this paper, the main research work and achievements are as follows:(1)We propose an algorithm for link prediction in the multi-relational networks based on random walk in the paper. In the algorithm, we first calculate similarity for every pair of nodes in each relation network, and define a transmission probability on every edge, which is equal to the summation of the similarities between the same two nodes connected by the edges in all the other relational networks. Then the similarity between nodes will spread and be updated in the form of random walk according to the transmission probability. Finally we get the similarity between nodes as the result of link prediction score. The experimental results show that our algorithm for the multi-relational networks has a more accurate prediction results than other algorithms.(2)We propose a link prediction algorithm for the multi-relational networks based on nodes influence. In the algorithm, we calculate the influence of every node in each relation network with the method of influence propagation, and form the feature vector of each relation network with nodes influence. The similarity between the different types of relations is defined as the similarity between their feature vectors. We combine the relation similarity and times of interactions between nodes to get the weight of each edge, link prediction is then performed on such weighted graph. Experiments show that our algorithm can obtain better predicting results than with other algorithms.(3)We propose a link prediction algorithm for the multi-relational networks based on community detection. We first calculate the similarity between different types of relations, and construct a weighted graph for the each type of relation. Then we detect the communities in the weighted graphs. We calculate the similarity between each pair of nodes and community centers respectively as the nodes initial similarity and community similarity. At last we get the link prediction score based on these two similarities. The experimental results show that our algorithm can achieve higher quality predicting results.