Actual Paper: http://arxiv.org/pdf/1011.4071.pdf
Citiation: Backstrom, Lars and Leskovec, Jure Supervised random walks: predicting and recommending links in social networks WSDM ’11
The link prediction problem is to identify any links that may be formed in future, or missing links in a network.
The challenge is to combine network structure and node/edge data. This problem is solved in this paper. Social networks are dynamic and they keep growing and studying a network at edge level is also interesting.
1. Real networks are extremely sparse.
2. How to use features of network to model links.
TO combine features of nodes and edges is challenging. Common approach followed in networks is to calculate no. of neighbors, degree of nodes, shortest between nodes etc.
In this paper, an Edge Strength Function is optimized using page-rank like random walk scores. This paper is very general and can be applied to a variety of domains.
1. Facebook, myspace.
2. Security – to predict hidden links in social network
3. Protien – protien interactions in system biology.
4. Give relavent pages to link to, for bloggers.
Challenge for many of the existing approaches is scalability.
First approach: Classification problem.
1. Class Imbalance – Few nodes are connected to a node, compared to not connected.
2. Feature Selection for Edges and Nodes.
3. Proximity – many possibilities like mentioned above.
Second Approach: Task is to rank the nodes.
This paper combines both of them.
Experiments are performed on synthetic data. ROC Curve is used for evaluation. Then real data sets are used for evaluation like FB, Co-authorship etc.
This method outperforms existing supervised models and far better than unsupervised models.
Leave a Reply