Privacy preservation method based on k-degree anonymity in social networks

To preserve the privacy of social networks,most existing methods are applied to satisfy different anonymity models,but some serious problems are involved such as often incurring large information losses and great structural modifications of original social network after being anonymized.Therefore,an improved privacy protection model called SimilarGraph is proposed,which is based on k-degree anonymous graph derived from k-anonymity to keep the network structure stable.Where the main idea of this model is firstly to partition network nodes into optimal number of clusters according to degree sequences based on dynamic programming,and then to reconstruct the network by means of moving edges to achieve k-degree anonymity with internal relations of nodes considered.To differentiate from traditional data disturbing or graph modifying method used by adding and deleting nodes or edges randomly,the superiority of our proposed scheme lies in which neither increases the number of nodes and edges in network,nor breaks the connectivity and relational structures of original network.Experimental results show that our SimilarGraph model can not only effectively improve the defense capability against malicious attacks based on node degrees,but also maintain stability of network structure.In addition,the cost of information losses due to anonymity is minimized ideally. © 2016, Chinese Institute of Electronics. All right reserved.