Finding your friends and following them to where you are
- 8 February 2012
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the fifth ACM international conference on Web search and data mining - WSDM '12
- p. 723-732
- https://doi.org/10.1145/2124295.2124380
Abstract
Location plays an essential role in our lives, bridging our online and offline worlds. This paper explores the interplay between people's location, interactions, and their social ties within a large real-world dataset. We present and evaluate Flap, a system that solves two intimately related tasks: link and location prediction in online social networks. For link prediction, Flap infers social ties by considering patterns in friendship formation, the content of people's messages, and user location. We show that while each component is a weak predictor of friendship alone, combining them results in a strong model, accurately identifying the majority of friendships. For location prediction, Flap implements a scalable probabilistic model of human mobility, where we treat users with known GPS positions as noisy sensors of the location of their friends. We explore supervised and unsupervised learning scenarios, and focus on the efficiency of both learning and inference. We evaluate Flap on a large sample of highly active users from two distinct geographical areas and show that it (1) reconstructs the entire friendship graph with high accuracy even when no edges are given; and (2) infers people's fine-grained location, even when they keep their data private and we can only access the location of their friends. Our models significantly outperform current comparable approaches to either task.Keywords
This publication has 15 references indexed in Scilit:
- Friendship and mobilityPublished by Association for Computing Machinery (ACM) ,2011
- Supervised random walksPublished by Association for Computing Machinery (ACM) ,2011
- Inferring social ties from geographic coincidencesProceedings of the National Academy of Sciences of the United States of America, 2010
- What is Twitter, a social network or a news media?Published by Association for Computing Machinery (ACM) ,2010
- Limits of Predictability in Human MobilityScience, 2010
- Why we twitterPublished by Association for Computing Machinery (ACM) ,2007
- Reality mining: sensing complex social systemsPersonal and Ubiquitous Computing, 2005
- Geographic routing in social networksProceedings of the National Academy of Sciences of the United States of America, 2005
- Modelling disease outbreaks in realistic urban social networksNature, 2004
- Deterministic annealing EM algorithmNeural Networks, 1998