Privacy-enhanced public view for social graphs

Hyoungshick Kim, Joseph Bonneau

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

Abstract

We consider the problem of releasing a limited public view of a sensitive graph which reveals at least k edges per node. We are motivated by Facebook's public search listings, which expose user profiles to search engines along with a fixed number of each user's friends. If this public view is produced by uniform random sampling, an adversary can accurately approximate many sensitive features of the original graph, including the degree of individual nodes. We propose several schemes to produce public views which hide degree information. We demonstrate the practicality of our schemes using real data and show that it is possible to mitigate inference of degree while still providing useful public views.

Original languageEnglish (US)
Title of host publication2nd ACM Workshop on Social Web Search and Mining, SWSM'09, Co-located with the 18th ACM International Conference on Information and Knowledge Management, CIKM 2009
Pages41-48
Number of pages8
DOIs
StatePublished - 2009
Event2nd ACM Workshop on Social Web Search and Mining, SWSM'09, Co-located with the 18th ACM International Conference on Information and Knowledge Management, CIKM 2009 - Hong Kong, China
Duration: Nov 2 2009Nov 6 2009

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Other

Other2nd ACM Workshop on Social Web Search and Mining, SWSM'09, Co-located with the 18th ACM International Conference on Information and Knowledge Management, CIKM 2009
CountryChina
CityHong Kong
Period11/2/0911/6/09

Keywords

  • Graph obfuscation
  • Privacy
  • Public view
  • Social networks

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Business, Management and Accounting(all)

Fingerprint Dive into the research topics of 'Privacy-enhanced public view for social graphs'. Together they form a unique fingerprint.

Cite this