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

Authors: Jun Yan; YuPan Tian; Hai Liu; ZhenQiang Wu

Addresses: School of Computer Science, Shaanxi Normal University, Xi'an 710119, China; School of Mathematics and Computer Applications, Shangluo College, Shangluo 726000, China ' School of Computer Science, Shaanxi Normal University, Xi'an 710119, China ' Guizhou Provincial Key Laboratory of Public Big Data, Guiyang 550025, China ' School of Computer Science, Shaanxi Normal University, Xi'an 710119, China

Abstract: 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.

Keywords: uncertain graph; k-edges differential privacy; random response mechanism; Laplace mechanism; link relationship.

DOI: 10.1504/IJSN.2022.122545

International Journal of Security and Networks, 2022 Vol.17 No.1, pp.28 - 38

Received: 29 Dec 2020
Accepted: 15 Jan 2021

Published online: 03 May 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article