Anonymizing bipartite graph data using safe groupings |
| |
Authors: | Graham Cormode Divesh Srivastava Ting Yu Qing Zhang |
| |
Affiliation: | 1. AT&T Labs-Research, Florham Park, NJ, USA 2. North Carolina State University, Raleigh, NC, USA 3. Teradata, El Segundo, CA, USA
|
| |
Abstract: | Private data often come in the form of associations between entities, such as customers and products bought from a pharmacy,
which are naturally represented in the form of a large, sparse bipartite graph. As with tabular data, it is desirable to be
able to publish anonymized versions of such data, to allow others to perform ad hoc analysis of aggregate graph properties.
However, existing tabular anonymization techniques do not give useful or meaningful results when applied to graphs: small
changes or masking of the edge structure can radically change aggregate graph properties. We introduce a new family of anonymizations
for bipartite graph data, called (k, ℓ)-groupings. These groupings preserve the underlying graph structure perfectly, and instead anonymize the mapping from entities
to nodes of the graph. We identify a class of “safe” (k, ℓ)-groupings that have provable guarantees to resist a variety of attacks, and show how to find such safe groupings. We perform
experiments on real bipartite graph data to study the utility of the anonymized version, and the impact of publishing alternate
groupings of the same graph data. Our experiments demonstrate that (k, ℓ)-groupings offer strong tradeoffs between privacy and utility. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|