High Utility K-anonymization for Social Network Publishing

Publication Type

Journal Article

Publication Date

12-2014

Abstract

Privacy and utility are two main desiderata of good sensitive information publishing schemes. For publishing social networks, many existing algorithms rely on k k -anonymity as a criterion to guarantee privacy protection. They reduce the utility loss by first using the degree sequence to model the structural properties of the original social network and then minimizing the changes on the degree sequence caused by the anonymization process. However, the degree sequence-based graph model is simple, and it fails to capture many important graph topological properties. Consequently, the existing anonymization algorithms that rely on this simple graph model to measure utility cannot guarantee generating anonymized social networks of high utility. In this paper, we propose novel utility measurements that are based on more complex community-based graph models. We also design a general k k -anonymization framework, which can be used with various utility measurements to achieve k k -anonymity with small utility loss on given social networks. Finally, we conduct extensive experimental evaluation on real datasets to evaluate the effectiveness of the new utility measurements proposed. The results demonstrate that our scheme achieves significant improvement on the utility of the anonymized social networks compared with the existing anonymization algorithms. The utility losses of many social network statistics of the anonymized social networks generated by our scheme are under 1 % in most cases.

Keywords

Social networks, Privacy, k k -Anonymity, Utility, HRG

Discipline

Communication Technology and New Media | Databases and Information Systems

Publication

Knowledge and Information Systems

Volume

41

Issue

3

First Page

697

Last Page

725

ISSN

0219-1377

Identifier

10.1007/s10115-013-0674-2

Publisher

Springer Verlag

Additional URL

http://dx.doi.org/10.1007/s10115-013-0674-2

Link to Full Text

Share

COinS