Preserving Privacy in Social Networks Against Connection Fingerprint Attacks

Publication Type

Conference Proceeding Article

Publication Date



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.


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


Computer Sciences | Databases and Information Systems

Research Areas

Data Management and Analytics


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

First Page


Last Page








City or Country

Piscataway, NJ

Additional URL