Uncertain graph generating approach based on differential privacy for preserving link relationship of social networks

摘要

With the widespread use of social networks in our daily life, the personal privacy in social networks has become a growing concern. To prevent the link relationship of social networks from disclosing users' sensitive information when the social networks data is released, an uncertain graph approach based on differential privacy is introduced, which can resist attacks based on background knowledge and possesses better data utility. In this approach, we propose modification of edges based on random response (MERR) algorithm and injection of uncertainty based on k -edges-differential privacy (IUDP) algorithm. The MERR algorithm can modify the edge of original graph according to random response mechanism, while the IUDP algorithm injects uncertainty to generate an uncertain graph. For evaluating our approach, the expectation of editing distance between two graphs is adapted to measure the level of privacy preserving. In addition, our approach is conducted in different datasets and compared with other approaches. The experimental results indicate that this approach achieves differential privacy and has better data utility.