Abstract
Online social networks (OSNs) like Facebook, and Myspace 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 net-work, being computationally prohibitive for huge-size social networks. In this paper, we define a basic node similar- ity measure that captures effectively local graph features. We also exploit global graph features introducing transitive node similarity. Moreover, we derive variants of our method that apply in signed networks. We perform extensive ex-perimental comparison of the proposed method against ex-isting recommendation algorithms using synthetic and real data sets (Facebook, Hi5 and Epinions). Our experimen-tal results show that our FriendTNS algorithm outperforms other approaches in terms of accuracy and it is also time e±cient. We show that a significant accuracy improvement can be gained by using information about both positive and negative edges. Copyright 2010 ACM.