The Library
Anonymizing bipartite graph data using safe groupings
Tools
Cormode, Graham, Srivastava, Divesh, Yu, Ting and Zhang, Qing (2010) Anonymizing bipartite graph data using safe groupings. VLDB Journal, Volume 19 (Number 1). pp. 115-139. doi:10.1007/s00778-009-0167-9 ISSN 1066-8888.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s00778-009-0167-9
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Query languages (Computer science), Privacy | ||||
Journal or Publication Title: | VLDB Journal | ||||
Publisher: | Springer Netherlands | ||||
ISSN: | 1066-8888 | ||||
Official Date: | February 2010 | ||||
Dates: |
|
||||
Volume: | Volume 19 | ||||
Number: | Number 1 | ||||
Number of Pages: | 25 | ||||
Page Range: | pp. 115-139 | ||||
DOI: | 10.1007/s00778-009-0167-9 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | National Science Foundation (U.S.) (NSF) | ||||
Grant number: | IIS-0430166 (NSF), CNS-0747247 (NSF) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |