Preserving Privacy in Social Networks Against Connection Fingerprint Attacks

Publication Type

Conference Proceeding Article

Publication Date

4-2015

Abstract

Existing works on identity privacy protection on social networks make the assumption that all the user identities in a social network are private and ignore the fact that in many real-world social networks, there exists a considerable amount of users such as celebrities, media users, and organization users whose identities are public. In this paper, we demonstrate that the presence of public users can cause serious damage to the identity privacy of other ordinary users. Motivated attackers can utilize the connection information of a user to some known public users to perform re-identification attacks, namely connection fingerprint (CFP) attacks. We propose two k-anonymization algorithms to protect a social network against the CFP attacks. One algorithm is based on adding dummy vertices. It can resist powerful attackers with the connection information of a user with the public users within n hops (n ≥ 1) and protect the centrality utility of public users. The other algorithm is based on edge modification. It is only able to resist attackers with the connection information of a user with the public users within 1 hop but preserves a rich spectrum of network utility. We perform comprehensive experiments on real-world networks and demonstrate that our algorithms are very efficient in terms of the running time and are able to generate k-anonymized networks with good utility.

Keywords

Edge modification, K-anonymization, Network utility, Privacy protection, Re identifications, Real-world networks, Running time, User identity

Discipline

Computer Sciences | Databases and Information Systems

Publication

2015 31st IEEE International Conference on Data Engineering, ICDE 2015: 13-17 April 2015, Seoul: Proceedings

First Page

54

Last Page

65

ISBN

9781479979639

Identifier

10.1109/ICDE.2015.7113272

Publisher

IEEE

City or Country

Piscataway, NJ

Additional URL

http://dx.doi.org/10.1109/ICDE.2015.7113272

Link to Full Text

Share

COinS