Difference between revisions of "Supervised Random Walk"
| Line 12: | Line 12: | ||
This method is used to recommend friends on [[UsesDataset::Facebook dataset]] and also in predicting links in collaboration network in [[UsesDataset::arXive]] database. | This method is used to recommend friends on [[UsesDataset::Facebook dataset]] and also in predicting links in collaboration network in [[UsesDataset::arXive]] database. | ||
== Method == | == Method == | ||
| − | + | Typically, [[UsesMethod:: Random walk with restart]] involves giving probabilities to every edge, which indicate the probability of taking that edge by a random walker given he is at any one of the node on either side of the edge. These probabilities decide which nodes are closer to the node from which we restart our random walks. One simple method that is to assign each edge out of a given node equal probability. However, ''supervised random walk'' presented in this paper provides the method to learn the probabilities so that the random walker restarting from node ''s'' is more likely to reach the "positive" nodes than "negative" nodes. Positive nodes are the one for which the links were formed in the training dataset and negative nodes are rest all nodes which are not connected the nodes ''s''. The method is formulated into an optimization problem for which an efficient estimation procedure is derived. | |
=== Problem Formulation === | === Problem Formulation === | ||
Revision as of 08:15, 30 March 2011
This is one of the paper discussed and written in course Social Media Analysis 10-802 in Spring 2011
Contents
Citation
Lars Backstrom & Jure Leskovec "Supervised Random Walks: Predicting and Recommending Links in Social Networks"
Online version
Summary
This paper addresses the problem of Link Prediction using the method of Random walk with restart. Supervised Random Walk is interesting because it ranks the nodes based the network information and also using rich node and edge attributes that exist in the dataset. The method is supervised learning task where the goal is to learn the parameters of the function that assigns the strength of the edge (probability of taking that edge) such that a random walker is more likely to reach nodes to which new links will be created in future.
This method is used to recommend friends on Facebook dataset and also in predicting links in collaboration network in arXive database.
Method
Typically, Random walk with restart involves giving probabilities to every edge, which indicate the probability of taking that edge by a random walker given he is at any one of the node on either side of the edge. These probabilities decide which nodes are closer to the node from which we restart our random walks. One simple method that is to assign each edge out of a given node equal probability. However, supervised random walk presented in this paper provides the method to learn the probabilities so that the random walker restarting from node s is more likely to reach the "positive" nodes than "negative" nodes. Positive nodes are the one for which the links were formed in the training dataset and negative nodes are rest all nodes which are not connected the nodes s. The method is formulated into an optimization problem for which an efficient estimation procedure is derived.
