Link Predictionin Social Networks:A Game Theory And Network Topology View

As an important way for people sharing information and communicating with each other, social networks contain a lot of valuable information about business and social behavior through analyzing and mining social network data. Link prediction, a core problem in social network research area, can predict the missing or new links. It plays an important role for understanding the dynamic evolution of social networks. However, most existing link prediction methods are based on network topology. Although these methods are simple and efficient, they are difficult to explain how the links form. To the best of our knowledge, this thesis is the first time to introduce the game theory idea into link prediction. It will regard the network users as game participants, and interaction between the users (with links and without links) as the users' strategy choice, in order to study users' rational strategy choice-It means under established choice by others, how to make their own benefit maximization. This is the approach for better explaining the process of users' rational choice in social activities, so as to make up the shortcoming of the existing link prediction with interpretability. It is also an important supplement for existing link prediction research. In this thesis, the main research is as follows:(1) Introduce a game-theoretic framework to address the link prediction problem based on the structures of social networks. We formulate the dynamics of link formation as a strategic game:Given an underlying social graph, we regard each user as a game participant, and the collection of potential neighbors as the strategy. Each user obtains game payoff according to his/her strategy. This is a non-cooperative game model, we use evolutionary approach to get the game result.(2) A new link prediction method based on node (NGLP) is proposed:It embodies the game model from the node view. According to the phenomenon of "the distance impacts on the link formations", we get each node's candidates, and assure that each node's strategy is the power set of his/her candidates. Each node obtains payoff through the local network topology, and independently determines its current choice according to the rule of "payoff maximization". Meanwhile, we proof that NGLP is a potential game under certain condition.(3) A new link prediction method based on edge (EGLP) is proposed:It embodies the game model from the edge view. We assume that the proposed EGLP game is an instance of a special subclass of multiplayer games, known as poly-matrix games, in which game participants are users of in the network and every edge denotes a two-participant game. The payoffs associated with each participant are additively separable so that the payoff of each player is given by the sum of the payoffs gained from each game played with one of its neighbor. Meanwhile, we proof that EGLP is a potential game under certain condition.(4) A new method to calculate the user's payoff is proposed:It utilizes orbit vector to record the information of user's local network topology, and weights all the orbits to get their influences, we call it power vector. At last, we get inner product of orbit vector and power vector, which is user's payoff.(5) Put forward a new filtering method named Gharmony:It filters the results rationally through calculating users' similarities. This method solves the possible problem that "the number of links obtained is greater than the size of test set".We realize this link prediction system, and verify the effectiveness through a lot of experiments. Experimental results on real-world datasets shows that NGLP/EGLP method is reasonable and effective.