{"id":391,"date":"2011-05-30T17:11:37","date_gmt":"2011-05-30T17:11:37","guid":{"rendered":"http:\/\/www.syslog.cl.cam.ac.uk\/?p=391"},"modified":"2011-05-30T17:13:34","modified_gmt":"2011-05-30T17:13:34","slug":"place-friends-designing-a-link-prediction-system-for-location-based-services","status":"publish","type":"post","link":"https:\/\/www.syslog.cl.cam.ac.uk\/2011\/05\/30\/place-friends-designing-a-link-prediction-system-for-location-based-services\/","title":{"rendered":"Place-Friends: designing a link prediction system for location-based services"},"content":{"rendered":"

Online social networks often deploy friend recommending systems, so that new users can be discovered and new social connections can be created.\u00c2\u00a0Since these service have easily millions of users, recommending friends potentially involves searching a huge prediction space: this is why platforms such as Facebook<\/a>, LinkedIn<\/a> and Twitter<\/a> 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.<\/p>\n

\"017\/365<\/a><\/p>\n

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<\/strong>.\u00c2\u00a0\u00c2\u00a0In a recent paper<\/a> which will appear at the upcoming ACM SIGKDD 2011 conference<\/a> we address the problem of designing a link prediction system which exploits the properties of the places that users visit.<\/p>\n

We analyze how Gowalla<\/a> users create social connections among them over a period of 4 months: \u00c2\u00a0we discover that about 30% of all new social links appear among users that check-in at the same places.<\/strong> Thus, these \u00e2\u20ac\u0153place- friends\u00e2\u20ac\u009d<\/strong><\/em> represent disconnected users that can become direct connections. \u00c2\u00a0By combining place-friends with the usual friends-of-friends of a user it is possible to\u00c2\u00a0make the prediction space about 15 times smaller and, yet, to cover about 66% of new social ties.<\/strong><\/p>\n

The challenge is then how to exploit the information given\u00c2\u00a0by 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\u00c2\u00a0the properties of the places where we interact can describe how likely we are to develop social ties with the people we interact with<\/strong>,\u00c2\u00a0as the sociological \u00e2\u20ac\u0153focus theory\u00e2\u20ac\u009d<\/a> put forward by Scott Feld in the early 80s suggests.<\/p>\n

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 <\/strong><\/em>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.<\/strong><\/p>\n

In summary, we are able to design an effective link prediction system with two important design choices:<\/p>\n