A secure K-automorphism privacy preserving approach with high data utility in social networks

The prevalence of social networks has raised the concern for individual privacy leakage. Although preserving user privacy in social networks has been studied extensively, there is still a lot of room for improvement in the state of the art techniques. For example, the recently proposed K-automorphism model can prevent node identity attack by constructing a K-automorphism graph; however, it ignores preserving the privacy of the edges, resulting in path length leakage and edge leakage in the anonymous graph. Another example is the K-isomorphism model, which was proposed to improve the K-automorphism model by transforming the graph of social networks into K disjoined isomorphic subgraphs. However, it cuts off the connection among subgraphs, which impairs the data utility of the released anonymous graph. In this paper, we design a secure and high utility privacy preserving model, called AK-secure, to prevent node identity attack, path length leakage, and edge leakage effectively. On the basis of the AK-secure privacy preserving model, we propose a graph anonymous algorithm, which constructs an anonymous graph satisfying the AK-secure privacy preserving model, minimizing information loss and guaranteeing high data utility. Extensive experiments on real data sets show the security, effectiveness of our AK-secure privacy preserving model and the high data utility of the released anonymous graph. Copyright © 2013 John Wiley & Sons, Ltd.