Place-Friends: designing a link prediction system for location-based services

Online social networks often deploy friend recommending systems, so that new users can be discovered and new social connections can be created. Since these service have easily millions of users, recommending friends potentially involves searching a huge prediction space: this is why platforms such as Facebook, LinkedIn and Twitter merely focus their prediction efforts on friends-of-friends, that is, on users that are only 2 hops away in the social network, sharing at least a common friend. Extending prediction efforts beyond this social circle is simply not worth it.

Nonetheless, in location-based social networks there is an unprecedented source of potential promising candidates for recommending new friends: the places where user check-in at.  In a recent paper which will appear at the upcoming ACM SIGKDD 2011 conference we address the problem of designing a link prediction system which exploits the properties of the places that users visit.

We analyze how Gowalla users create social connections among them over a period of 4 months:  we discover that about 30% of all new social links appear among users that check-in at the same places. Thus, these “place- friends” represent disconnected users that can become direct connections.  By combining place-friends with the usual friends-of-friends of a user it is possible to make the prediction space about 15 times smaller and, yet, to cover about 66% of new social ties.

The challenge is then how to exploit the information given by the check-ins of two users who visit the same places to predict whether they will establish a direct connection or not. It turns out that the properties of the places where we interact can describe how likely we are to develop social ties with the people we interact with, as the sociological “focus theory” put forward by Scott Feld in the early 80s suggests.

Hence, we define prediction features which quantify users that are likely to become friends considering the places they visit and the properties of these places. For instance, we consider the entropy of a place to find venues that are more likely to foster social bonds, such as offices, gyms and schools rather than museums and football stadiums: when two users both visit a place with low entropy it is highly likely that they will develop a social connection.

In summary, we are able to design an effective link prediction system with two important design choices:

• focusing link prediction only on a reduced set of candidates;
• exploiting location-based user activity to define successful prediction features.

These two simple ideas are able to improve the overall performance of link prediction systems on location-based services: as a consequence, real-world systems can be deployed to use the predicted links to suggest friends and keep users interested.

Exploiting Place Features in Link Prediction on Location-based Social Networks

Salvatore Scellato, Anastasios Noulas, Cecilia Mascolo. - In Proceedings of 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2011). San Diego, USA. August 2011.  [PDF]