Discretionary Social Network Data Revelation with a User-Centric Utility Guarantee
No Thumbnail Available
Date
2012-08-08
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The proliferation of online social networks has created intense interest in studying the nature of such networks and revealing network information of interest to the end user. At the same time, the revelation of such data raises privacy concerns. Existing research addresses this problem following an approach popular in the database community: a model of data privacy is defined, and the data is rendered in a form that satisfies the constraints of that model while aiming to maximize some utility measure. Still, these is no consensus on what constitutes a clear and quantifiable utility measure over graph data. In this paper, we take a different approach: instead of starting out with a privacy objective, we define a utility guarantee, in terms of certain graph connectivity properties being preserved, that should be respected when releasing data, while otherwise distorting the graph to an extend desired for the sake of confidentiality. We propose a form of data release which builds on current practice in social network platforms: A user may want to see a subgraph of the whole network graph, in which that user as well as distant connections and affliates participate. Such a snapshot should not allow malicious users to gain private information, yet provide useful information for benevolent users. We propose a mechanism to prepare data for user view under this setting. In an experimental study with real-world data, we demonstrate that our method preserves graph properties of interest (e.g., clustering coefficient, shortest path length, diameter, radius) more successfully than methods that randomly distort the graph to an equal extent, while it withstands structural attacks proposed in the literature.