A Study Of Link Prediction Problem In Online Social Network

In real world, many systems of social, biological, and information can be described by network. In the network, we use nodes to represent individual entities and use edges to represent the relationship or interaction between the nodes. Recently, with the development of information technology, there are more and more popular online social networks existing. Social network, as a typical application of Web2.0, provides a new way of interaction between people, and provides a new way for information sharing and communication through the link between users on the Internet platform.Social network is going to change over time. How to make use of existing information to predict the new links in network effectively is not only a fundamental problem in network analysis, but also an important application in the field of popular commercial social network sites now. In online social network, we can understand the causes of relationship between social users better through effective link prediction algorithm, and filter nodes of all in the network by predicting results to recommend user information of their interest. The existing link prediction algorithms mainly focus on the characteristics of the structure of the network, but not on giving a good description of user’s interest and the characteristics. In this thesis, we study the link prediction problem in social network, the main work and contributions are as follows:1) Using supervised random walk algorithm computes probability of link generation between nodes in network and then makes top-K recommendation. In the algorithm, properties of the nodes and edges are weighted to calculate the strength of the network edge, then using the strength to bias random walk in social network, the score of the random walk is probability of new links between users. In this thesis, we selected the users’properties, as well as the interaction between the nodes and other information as features, and give some analyses of these features.2) In content-oriented social network, the user’s interest will affect the link generation between users. Through the analysis of data of users’behavior, we model the user interests, and generate candidate set of the users with similar interest. In this way, through the pre-filtering process, we not only help users find others they are interested in, but also reduce the number of candidate sets, improve the efficiency of algorithm. 3) The experiments on data of social media network in real world verify the effectiveness of our proposed algorithm.