Online social networks such as Facebook, Twitter and Google Plus often deploy friend recommending systems, so that new users can be discovered and new social connections can be created. Since these services have millions of users, recommending friends potentially involves searching a needle in a haystack: this is why these platforms merely focus their prediction efforts on 'friends-of-friends', that is, on users sharing at least a common friend. Extending prediction efforts beyond this social circle is simply not worth it.
Nonetheless, in location-based social networks such as Foursquare there is an unprecedented source of potential promising candidates for recommending new friends: the places where users check-in at. A recent paper written with my colleagues at the University of Cambridge addresses the problem of designing a link prediction system exploiting the properties of the places that users visit.
In our research we analysed the location-based social network Gowalla to see how its users created social connections over a period of four months: we discovered 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 user check-ins to predict social connections. It turns out that the properties of the places where we interact can determine how likely we are to develop social ties there. Offices, gyms and schools are more likely to aid development rather than other places such as football stadiums, museums or airports. In those places, it's highly unlikely people will develop a social connection, as suggested by the sociological "focus theory" put forward by Scott Feld in the early 80s. Hence, we compute the entropy of a place to automatically find such venues that are more likely to foster social bonds and build a prediction system.The results show how it is possible to improve the performance of link prediction systems by considering where people go, thus keeping the users of these services interested and engaged. Our research will be presented in San Diego at the upcoming ACM SIGKDD 2011conference.