Transitive node similarity: predicting and recommending links in signed social networks

Online social networks (OSNs) like Facebook, Myspace, and Hi5 have become popular, because they allow users to easily share content. OSNs recommend new friends to registered users based on local features of the graph (i.e., based on the number of common friends that two users share). However, OSNs do not exploit the whole structure of the network. Instead, they consider only pathways of maximum length 2 between a user and his candidate friends. On the other hand, there are global approaches, which detect the overall path structure in a network, being computationally prohibitive for huge-size social networks. In this paper, we define a basic node similarity measure that captures effectively local graph features (i.e., by measuring proximity between nodes). We exploit global graph features (i.e., by weighting paths that connect two nodes) introducing transitive node similarity. We also derive variants of our method that apply to different types of networks (directed/undirected and signed/unsigned). We perform extensive experimental comparison of the proposed method against existing recommendation algorithms using synthetic and real data sets (Facebook, Hi5 and Epinions). Our experimental results show that our FriendTNS algorithm outperforms other approaches in terms of accuracy and it is also time efficient. Finally, we show that a significant accuracy improvement can be gained by using information about both positive and negative edges.