Graph partition based privacy-preserving scheme in social networks

Abstract With the development of social networks, more and more data about users are released on social platforms such as Facebook, Enron, WeChat, in terms of social graphs. Without the efficient anonymization, the graph data publishing will cause serious privacy leakage of users, for example, malicious attackers might launch 1-neighborhood graph attack on targets, which assumes that 1-hop neighbors and the relations among them are known by attackers, thereby, targets can be re-identified in anonymous social graphs. To prevent such attack, we propose a Graph Partition based Privacy-preserving Scheme, named GPPS,i n social networks to realize social graph anonymization. The proposed GPPS preserves users’ identity privacy by k-anonymity which achieved by node clustering and graph modification. Specifically, in the similarity matrix calculation, we introduce the degree-based graph entropy to improve the accuracy of node clustering. Then, the graph modification is implemented to achieve the k-anonymity of users and meanwhile minimize the graph information loss. The experiment results illustrate that the proposed GPPS is effective and efficient both on synthetic and real data sets.