Affinity prediction in online social networks

Abstract

Link prediction is the problem of inferring whether potential edges between pairs of vertices in a graph will be present or absent in the near future. To perform this task it is usual to use information provided by a number of available and observed vertices/edges. Then, a number of edge scoring methods based on this information can be created. Usually, these methods assess local structures of the observed graph, assuming that closer vertices in the original period of observation will be more likely to form a link in the future. In this paper we explore the combination of local and global features to conduct link prediction in online social networks. The contributions of the paper are twofold: (a) We evaluate a number of strategies that combines global and local features tackling the locality assumption of link prediction scoring methods, and (b) We only use network topology-based features, avoiding the inclusion of informational or transactional based features that involve heavy computational costs in the methods. We evaluate our proposal using real-world data provided by Skout Inc.1, an affinity online social network with millions of users around the world. Our results show that our proposal is feasible.