Eight friends are enough: Social graph approximation via public listings

Joseph Bonneau, Jonathan Anderson, Ross Anderson, Frank Stajano

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The popular social networking website Facebook exposes a "public view" of user profiles to search engines which includes eight of the user's friendship links. We examine what interesting properties of the complete social graph can be inferred from this public view. In experiments on real social network data, we were able to accurately approximate the degree and centrality of nodes, compute small dominating sets, find short paths between users, and detect community structure. This work demonstrates that it is difficult to safely reveal limited information about a social network.

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09
Pages13-18
Number of pages6
DOIs
StatePublished - 2009
Event2nd ACM EuroSys Workshop on Social Network Systems, SNS '09 - Nuremberg, Germany
Duration: Mar 31 2009Mar 31 2009

Publication series

NameProceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09

Other

Other2nd ACM EuroSys Workshop on Social Network Systems, SNS '09
CountryGermany
CityNuremberg
Period3/31/093/31/09

Keywords

  • Data breaches
  • Graph theory
  • Privacy
  • Social networks
  • Web crawling

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Software

Fingerprint Dive into the research topics of 'Eight friends are enough: Social graph approximation via public listings'. Together they form a unique fingerprint.

  • Cite this

    Bonneau, J., Anderson, J., Anderson, R., & Stajano, F. (2009). Eight friends are enough: Social graph approximation via public listings. In Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09 (pp. 13-18). (Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09). https://doi.org/10.1145/1578002.1578005