Privacy-Enhanced Public View for Social Graphs

Free registration required

Executive Summary

The authors consider the problem of releasing a limited public view of a sensitive graph which reveals at least k edges per node. They 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. They propose several schemes to produce public views which hide degree information. They demonstrate the practicality of their schemes using real data and show that it is possible to mitigate inference of degree while still providing useful public views.

  • Format: PDF
  • Size: 212.7 KB