基于三元闭包的不确定图差分隐私保护算法

Differential privacy algorithm of uncertain graph based on ternary closure

在社交网络的隐私保护中,针对三元闭包算法存在无法提供可控的隐私保护和无法抵御背景知识攻击的问题,结合差分隐私技术,提出基于三元闭包的不确定图差分隐私保护改进算法。改进算法首先利用三元闭包原理对原始社交网络图进行加边形成三角形,然后对三角形的边赋予符合拉普拉斯分布的存在概率,最后,根据社交网络图中每条边的存在概率生成新的社交网络图。改进算法将差分隐私应用于保护社交网络图的边关系,不仅提供了可控的隐私保护,而且可以抵御背景知识攻击。理论证明,改进算法满足差分隐私,针对算法的隐私保护性分析设计了一个基于信息熵的实验,实验结果表明,改进算法的隐私保护性优于三元闭包算法,适合需要更高隐私保护性的场景。

In the privacy protection of social networks,ternary closure algorithm has some problems,such as being unable to provide controllable privacy protection and resist background knowledge attacks.To solve these problems,an improved algorithm is proposed combined with differential privacy technology-differential privacy protection algorithm for uncertain graphs based on ternary closure.Firstly,the improved algorithm firstly uses the ternary closure principle to edge the original social network graph to form a triangle;Secondly,the improved algorithm assigns the existence probability of Laplace distribution to the edges of triangles;Finally,the improved algorithm will generate a new social network graph according to the existence probability of each edge in the social network graph.Because the improved algorithm applies differential privacy to protect the edge relationship of social network graph,it can not only provide controllable privacy protection,but also resist background knowledge attack.Since it can be proved theoretically that the improved algorithm satisfies differential privacy,an experiment based on information entropy is designed for the privacy protection analysis of the algorithm.The experimental results show that the privacy protection of the improved algorithm is better than that of the ternary closure algorithm,and it is suitable for scenes requiring higher privacy protection.