Generating Synthetic Graphs for Large Sensitive and Correlated Social Networks

With the fast development of social networks, there exists a huge amount of users information as well as their social ties. Such information generally contains sensitive and correlated users' personal data. How to accurately analyze this large and correlated social graph data while protecting users' privacy has become a challenging research issue. In the literature, various research efforts have been made on this topic. Unfortunately, correlation based privacy protection techniques for social graph data have seldom been investigated. To the best of our knowledge, this paper is the first attempt to resolve this research issue. Particularly, this paper first protects users' raw data via local differential privacy technique and then a correlation based privacy protection approach is designed. Last, a K-means algorithm is applied on the perturbed local data and the clustering results are used to generate the synthetic graphs for further data analytics. Experiments are evaluated on two real-world data sets, i.e. Facebook dataset and Enron dataset, and the promising experimental results demonstrate that the proposed approach is superior to the state-of-the-art LDPGen and the baseline method, e.g. the DGG, with respect to the accuracy and utility evaluation criteria.