Research On Methods Of Link Prediction In Social Networks

With the rapid growth of Web 2.0 and computer networks, social networks have become mainstream media and allowed people to share information, express opinions and make friends. While social networks provide service and convenience to their users, they also record behavioral data. By analyzing and mining behavioral data recorded in social networks,we can uncover the underlying value of these data. Social network providers can use the findings from these data to provide better services and meet the demand of users.As one of the most important problems in network science and data mining, link prediction has attracted increasing attention from the computer science, mathematics, and sociology communities. The goal of link prediction is to estimate the likelihood of the existence of a link between two nodes on the basis of the observed links and the attributes of the nodes.Link prediction has a strong theoretical value and broad application prospect. In theory, link prediction can provide a better understanding of the evolution mechanism of a social network and enrich the theories in network science. In application, link prediction has several important applications, including friend recommendation, attitude inference, and personalized recommendation.Recently, link prediction in social networks has been of great concern;however, many issue to be the problem of non-generalization of the link prediction method, the low accuracy of the prediction, and the difficulty to adapt the method to large-scale networks. In addition, the network data used for link prediction often suffer from single data source, sparse connection of the known trust relation and simple edge attribute expression.Therefore, this dissertation focuses on link prediction in social networks as one of the core problems and intensively analyzes and studies this problem by breaking it down into three subproblems. By integrating mathematical analysis as well as complex network and machine learning theory and technology, we propose four link prediction methods, which can improve the prediction effect. Our proposed methods can solve the problem of link prediction in many universal networks, signed networks and social rating networks. The main work and innovation of this dissertation are as follows:(1) In the framework of node similarity, we proposed a model based on 2 and 3 hops common neighbors to predict missing links in complex networks. The advantage of this model is that it can well distinguish the different roles of common neighbors and assign these common neighbors different weights. Moreover, this model exploit both 2 and 3 hops common neighbors, more accurate similarity score can be attained to predict missing links. To test our model, we compare three representative local indices and a global path index on six real-world networks. Extensive analysis on six real-world networks shows that our proposed model outperform other state-of-the-art methods.(2) In order to make the link sign prediction more accurate in signed networks, it is necessary to analyses each underlying principle of generating signed networks. Structure balance theory and status theory are extended to gain more information for link sign prediction. A new measurement named PageTrust in web network is introduced to describe the importance of node of signed networks. On the basis of integrating different kind principles of generating signed networks, a group of refined features are extracted. Based on those creative features, two link sign predictors using supervised machine learning algorithms are established.Experimental results on two real signed networks demonstrate that learned model is more accurate and generalized than other state-of-the-art methods.(3) Trust prediction and information item rating are two fundamental tasks for social rating network systems. In response to improve the prediction accuracy of the two basic problems encountered in the data sparsity of trust relation and information item rating, we present a joint rating and trust prediction model based on collective matrix factorization.In our model, trust relation matrix and information rating matrix are factorized into latent features matrixes collectively. We can make full use of correspondence among users and information items by sharing latent user feature. Moreover, our model can capture the data dependent effect of trust domains and rating domain separately. By using those learned latent features matrixes multiplication, we can obtain predictions of trust and rating. Experimental results on two real network data demonstrate that our model is more accurate than other state-of-the-art methods.(4) To improve trust prediction performance and alleviate the sparsity of explicit trust graph, we aggregate heterogeneous networks from both an explicit trust graph and a rating graph and exploit the effect of cluster-level trust prediction. In this dissertation, we propose a framework incorporating co-clustering users and item methods and aggregating of multi-model similarity of users. We first co-cluster users and items to obtain several meaningful user-item subgroups. In these subgroups, user preference on items subset is more accurate and consistent. Then, in each subgroup, we separately calculate explicit and implicit similarities between two users.Explicit similarity is achieved through Katz method based on the explicit trust graph; however, implicit similarity is calculated by our proposed method based on the rating graph. Moreover, we combine explicit and implicit similarities using a linear combination method. User pairs may belong to one or more subgroups. Therefore, we merge all aggregated similarity from all belonging subgroups to achieve trust prediction.Experimental results on three real-world datasets show that proposed framework can obtain a significant improvement in terms of prediction accuracy criteria over representative approaches.