An Uncertain Graph Method Based on Node Random Response to Preserve Link Privacy of Social Networks

• Jun Yan,
• Jiawang Chen,
• Yihui Zhou,
• Zhenqiang Wu,
• Laifeng Lu,

Vol. 18, No. 1, January 31, 2024
10.3837/tiis.2024.01.009, Download Paper (Free):

• Social Networks
• link privacy
• uncertain graph
• Differential privacy
• random response

Abstract

In pace with the development of network technology at lightning speed， social networks have been extensively applied in our lives. However, as social networks retain a large number of users’ sensitive information, the openness of this information makes social networks vulnerable to attacks by malicious attackers. To preserve the link privacy of individuals in social networks, an uncertain graph method based on node random response is devised, which satisfies differential privacy while maintaining expected data utility. In this method, to achieve privacy preserving, the random response is applied on nodes to achieve edge modification on an original graph and node differential privacy is introduced to inject uncertainty on the edges. Simultaneously, to keep data utility, a divide and conquer strategy is adopted to decompose the original graph into many sub-graphs and each sub-graph is dealt with separately. In particular, only some larger sub-graphs selected by the exponent mechanism are modified, which further reduces the perturbation to the original graph. The presented method is proven to satisfy differential privacy. The performances of experiments demonstrate that this uncertain graph method can effectively provide a strict privacy guarantee and maintain data utility.

Statistics

Cite this article