Graph partition based privacy-preserving scheme in social networks

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 degreebased 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.

Automated summary

This study proposes a Graph Partition based Privacy-preserving Scheme (GPPS) to anonymize users' identities in social networks through node clustering and graph modification, achieving k-anonymity to reduce privacy risks. By introducing degree-based graph entropy in similarity matrix calculation, accurate node clustering is achieved, and graph modification further ensures k-anonymity while minimizing information loss, proving to be effective and efficient on both synthetic and real datasets.