Spectral clustering for link prediction in social networks with positive and negative links

Online social networks (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). Real OSNs (e.g. Facebook) do not exploit all network structure. Instead, they consider only pathways of maximum length 2 between a user and his candidate friends. This can limit the accuracy of prediction. 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 provide friend recommendations, by performing multi-way spectral clustering, which uses information obtained from the top few eigenvectors and eigenvalues of the normalized Laplacian matrix and computes a multi-way partition of the data. As a result, it produces a less noisy matrix, which is smaller and more compact than the original one, focusing on main linking trends of the social network. Thus, we are able to provide fast and more accurate friend recommendations. Moreover, spectral clustering compared to traditional clustering algorithms, such as k-means and DBSCAN, which assume globular (convex) regions in Euclidean space, is more flexible, in capturing the non-connected components of a social graph and a wider range of cluster geometries. We perform an extensive experimental comparison of the proposed method against existing link prediction algorithms, the k-means and two-way nCut clustering algorithms, using synthetic and three real data sets (Hi5, Facebook, and Epinions). Our experimental results show that our SpectralLink algorithm outperforms the local approaches, the k-means and two-way nCut clustering algorithms in terms of effectiveness, whereas it is more efficient than the global approaches. We show that a significant accuracy improvement can be gained by using information about both positive and negative edges.