skip to main content
10.1145/1772690.1772698acmotherconferencesArticle/Chapter ViewAbstractPublication PageswwwConference Proceedingsconference-collections
research-article

Find me if you can: improving geographical prediction with social and spatial proximity

Published:26 April 2010Publication History

ABSTRACT

Geography and social relationships are inextricably intertwined; the people we interact with on a daily basis almost always live near us. As people spend more time online, data regarding these two dimensions -- geography and social relationships -- are becoming increasingly precise, allowing us to build reliable models to describe their interaction. These models have important implications in the design of location-based services, security intrusion detection, and social media supporting local communities.

Using user-supplied address data and the network of associations between members of the Facebook social network, we can directly observe and measure the relationship between geography and friendship. Using these measurements, we introduce an algorithm that predicts the location of an individual from a sparse set of located users with performance that exceeds IP-based geolocation. This algorithm is efficient and scalable, and could be run on a network containing hundreds of millions of users.

References

  1. L. Adamic, R. Lukose, A. Puniyani, and B. Huberman. Search in power-law networks. Physical review E, 64(4):46135, 2001.Google ScholarGoogle Scholar
  2. L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 44--54, New York, NY, USA, 2006. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. L. Backstrom, J. Kleinberg, R. Kumar, and J. Novak. Spatial variation in search engine queries. In WWW '08: Proceeding of the 17th international conference on World Wide Web, pages 357--366, New York, NY, USA, 2008. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. C. Butts. Predictability of large-scale spatially embedded networks. In Dynamic Social Network Modeling and Analysis: workshop summary and papers, pages 313--323, 2003.Google ScholarGoogle Scholar
  5. D. Crandall, L. Backstrom, D. Huttenlocher, and J. Kleinberg. Mapping the world's photos. In WWW, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. R. Dhamija, J. D. Tygar, and M. Hearst. Why phishing works. In CHI '06: Proceedings of the SIGCHI conference on Human Factors in computing systems, pages 581--590, New York, NY, USA, 2006. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. L. Festinger, S. Schachter, and K. Back. Social pressures in informal groups: A study of human factors in housing. Stanford Univ Pr, 1963.Google ScholarGoogle Scholar
  8. E. Gilbert, K. Karahalios, and C. Sandvig. The network in the garden: an empirical analysis of social media in rural life. In CHI '08: Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, pages 1603--1612, New York, NY, USA, 2008. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. S. Graham. The end of geography or the explosion of place? Conceptualizing space, place and information technology. Progress in human geography, 22(2):165, 1998.Google ScholarGoogle Scholar
  10. A. Khalil and K. Connelly. Context-aware telephony: privacy preferences and sharing patterns. In CSCW '06: Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, pages 469--478, New York, NY, USA, 2006. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. J. Kleinberg. Navigation in a small world. Nature, 406(6798):845--845, 2000.Google ScholarGoogle ScholarCross RefCross Ref
  12. J. Kleinberg. The small-world phenomenon: an algorithm perspective. In STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 163--170, New York, NY, USA, 2000. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, page 617. ACM, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 462--470. ACM, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. Proceedings of the National Academy of Sciences, 102(33):11623, 2005.Google ScholarGoogle ScholarCross RefCross Ref
  16. MaxMind, Inc. GeoIP City Accuracy for Selected Countries, November 2008. http://www.maxmind.com/app/city_accuracy.Google ScholarGoogle Scholar
  17. B. Mayhew and R. Levinger. Size and the density of interaction in human aggregates. The American Journal of Sociology, 82(1):86--110, 1976.Google ScholarGoogle ScholarCross RefCross Ref
  18. D. Mok and B. Wellman. Did distance matter before the Internet? Interpersonal contact and support in the 1970s. Social networks, 29(3):430--461, 2007.Google ScholarGoogle ScholarCross RefCross Ref
  19. L. Nahemow and M. Lawton. Similarity and propinquity in friendship formation. Journal of Personality and Social Psychology, 32(2):205--213, 1975.Google ScholarGoogle ScholarCross RefCross Ref
  20. J. Q. Stewart. An inverse distance variation for certain social influences. Science, 93(2404):89--90, 1941.Google ScholarGoogle ScholarCross RefCross Ref
  21. U.S. Census Bureau. Census 2000 Summary File 1, 2000. http://factfinder.census.gov/servlet/ DCGeoSelectServlet?ds_name=DEC_2000_SF1_U.Google ScholarGoogle Scholar
  22. U.S. Census Bureau. Redistricting Census 2000 TIGER/Line Files, 2000. http://www.census.gov/ geo/www/tiger/tiger2k/tgr2000.html.Google ScholarGoogle Scholar

Index Terms

  1. Find me if you can: improving geographical prediction with social and spatial proximity

              Recommendations

              Comments

              Login options

              Check if you have access through your login credentials or your institution to get full access on this article.

              Sign in
              • Published in

                cover image ACM Other conferences
                WWW '10: Proceedings of the 19th international conference on World wide web
                April 2010
                1407 pages
                ISBN:9781605587998
                DOI:10.1145/1772690

                Copyright © 2010 International World Wide Web Conference Committee (IW3C2)

                Publisher

                Association for Computing Machinery

                New York, NY, United States

                Publication History

                • Published: 26 April 2010

                Permissions

                Request permissions about this article.

                Request Permissions

                Check for updates

                Qualifiers

                • research-article

                Acceptance Rates

                Overall Acceptance Rate1,899of8,196submissions,23%

              PDF Format

              View or Download as a PDF file.

              PDF

              eReader

              View online with eReader.

              eReader

              ePub

              View this article in ePub.

              View ePub