Actual Paper: http://www.islab.ntua.gr/attachments/article/63/06033365.pdf
Link predictions is done as a classification problem for a competition. 94 features were calculated and they are given as input for Random forests for classification. ROC is used for evaluation.
Study of network dynamics has numerous applications like marketers use it to recommend products to a person based on his contacts. Graph representation allows to use power of existing graph theory to solve this problem. This paper deals each edge as friendship and node as user. (In our project, each node is photo and edge is relationship between them.).
This problem is classification where prediction is find if link exists or not, but in real world it would be, which node has more probability of creating links with others and with which other nodes it has more probability of creating links.
In this paper, different similarity scores are considered as features. Scores should be normalized to a common scale wherever possible.
Instead of using the entire graph at once, sub-graphs are used to find prediction for a pair of nodes. A Sub graph for a pair of nodes is created by considering the neighbor nodes of those two nodes and constructing a graph with edges between such nodes. This can be done at different levels.
Score is calculated by considering top 10 related nodes of a node A, and then finding the intersection of those 10 nodes with the neighbour nodes of node B and calculating the sum of similarity of those intersection nodes and the node A. When there are fewer friends for a node, it is difficult to get proper semantics, so neighbour nodes are considered. But calculating the top 10 friends for Node A can be expensive.
Weights for edges between pair of nodes is calculated based on the degree of the nodes.
w = 1 / (sqrt(1+degree))
Using this weights, nearest neigbours were found.
ROC is used for evaluation.
Feasibilty, scalability and accuracy must be balanced.
Leave a Reply