Adam Sadilek
Henry Kautz
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.
Supplemental Material
- L. Backstrom and J. Leskovec. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international conference on Web search and data mining, pages 635--644. ACM, 2011. Google Scholar
Digital Library
- L. Backstrom, E. Sun, and C. Marlow. Find me if you can: improving geographical prediction with social and spatial proximity. In Proceedings of the 19th international conference on World wide web, pages 61--70. ACM, 2010. Google ScholarDigital Library
- R. Bell, Y. Koren, and C. Volinsky. Modeling relationships at multiple scales to improve accuracy of large recommender systems. In KDD, pages 95--104, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- L. Breiman et al. Classification and Regression Trees. Chapman & Hall, New York, 1984.Google Scholar
- A. B. Brush, J. Krumm, and J. Scott. Exploring end user preferences for location obfuscation, location-based services, and the value of location. In Ubicomp, Ubicomp '10, pages 95--104, New York, NY, USA, 2010. ACM. Google ScholarDigital Library
- E. Cho, S. A. Myers, and J. Leskovec. Friendship and mobility: User movement in location-based social networks. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2011. Google ScholarDigital Library
- D. Crandall, L. Backstrom, D. Cosley, S. Suri, D. Huttenlocher, and J. Kleinberg. Inferring social ties from geographic coincidences. Proceedings of the National Academy of Sciences, 107(52):22436, 2010.Google ScholarCross Ref
- M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pages 253--262. ACM, 2004. Google ScholarDigital Library
- A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society, 39(1):1--38, 1977.Google Scholar
- N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing, 10(4):255--268, 2006. Google ScholarDigital Library
- D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010. Google ScholarDigital Library
- S. Eubank, H. Guclu, V. Anil Kumar, M. Marathe, A. Srinivasan, Z. Toroczkai, and N. Wang. Modelling disease outbreaks in realistic urban social networks. Nature, 429(6988):180--184, 2004.Google ScholarCross Ref
- Z. Ghahramani. Learning dynamic Bayesian networks. In Adaptive Processing of Sequences and Data Structures, page 168. Springer, 1998. Google ScholarDigital Library
- A. Gruzd, B. Wellman, and Y. Takhteyev. Imagining twitter as an imagined community. In American Behavioral Scientist, Special issue on Imagined Communities, 2011.Google Scholar
- L. Hong, B. Suh, and E. H. Chi. Tweets from justin bieber's heart: the dynamics of the "location" field in user profiles. In ACM CHI, 2011.Google Scholar
- A. Java, X. Song, T. Finin, and B. Tseng. Why we twitter: understanding microblogging usage and communities. In WebKDD/SNA-KDD, pages 56--65, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- M. Jordan. Learning in graphical models. Kluwer Academic Publishers, 1998. Google ScholarDigital Library
- H. Kwak, C. Lee, H. Park, and S. Moon. What is Twitter, a Social Network or a News Media? In WWW, April 2010. Google ScholarDigital Library
- D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol., 58:1019--1031, May 2007. Google ScholarDigital Library
- D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. Proceedings of the National Academy of Sciences of the United States of America, 102(33):11623, 2005.Google ScholarCross Ref
- K. Murphy. Dynamic bayesian networks: representation, inference and learning. PhD thesis, University of California, Berkeley, 2002. Google ScholarDigital Library
- K. P. Murphy, Y. Weiss, and M. I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In In Proceedings of Uncertainty in AI, pages 467--475, 1999. Google ScholarDigital Library
- J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988. Google ScholarDigital Library
- A. S. Pentland. Honest Signals: How They Shape Our World. The MIT Press, 2008. Google ScholarDigital Library
- S. Scellato, A. Noulas, R. Lambiotte, and C. Mascolo. Socio-spatial properties of online location-based social networks. Proceedings of ICWSM, 11, 2011.Google Scholar
- D. Smith and J. Eisner. Dependency parsing by belief propagation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 145--156. Association for Computational Linguistics, 2008. Google ScholarDigital Library
- C. Song, Z. Qu, N. Blumm, and A. Barabási. Limits of predictability in human mobility. Science, 327(5968):1018, 2010.Google ScholarCross Ref
- B. Taskar, M.-F. Wong, P. Abbeel, and D. Koller. Link prediction in relational data. In in Neural Information Processing Systems, 2003.Google Scholar
- N. Ueda and R. Nakano. Deterministic annealing em algorithm. Neural Networks, 11(2):271--282, 1998. Google ScholarDigital Library
Index Terms
- Finding your friends and following them to where you are
Recommendations
Finding Popular Friends in Social Networks
CGC '12: Proceedings of the 2012 Second International Conference on Cloud and Green ComputingThe emergence of social computing enables users to intersect social behaviour with computing systems and to create social conventions as well as social contexts through the use of software and technology. Social networking sites have become popular to ...
Social Link Prediction in Online Social Tagging Systems
Social networks have become a popular medium for people to communicate and distribute ideas, content, news, and advertisements. Social content annotation has naturally emerged as a method of categorization and filtering of online information. The ...
Finding Strong Groups of Friends among Friends in Social Networks
DASC '11: Proceedings of the 2011 IEEE Ninth International Conference on Dependable, Autonomic and Secure ComputingOver the past few years, the rapid growth and the exponential use of social digital media has led to an increase in popularity of social networks and the emergence of social computing. In general, social networks are structures made of social entities (...
Comments