AAAI Publications, Workshops at the Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Games of Friends: A Game-Theoretical Approach for Link Prediction in Online Social Networks
Giovanni Zappella, Alexandros Karatzoglou, Linas Baltrunas

Last modified: 2013-06-29


Online Social Networks (OSN) have enriched the social lives of millions of users. Discovering new friends in the social network is valuable both for the user and for the health of OSN since users with more friends engage longer and more often with the site. The simplest way to formalize friendship recommendation is to cast the problem as a link prediction problem in the social graph. In this work we introduce a game-theoretical approach based on the Graph Transduction Game. It scales with ease beyond 13 million of users and was tested on a real world data from Tuenti OSN. We utilize the social graph and several other graphs that naturally arise in Tuenti such as the wall-to-wall post graph. We compare our approach to standard local measures and demonstrate a significant performance benefit in terms of mean average precision and reciprocal rank.


social network; large scale; link prediction

Full Text: PDF