社交网络下的不确定图隐私保护算法

Privacy Preserving Algorithms of Uncertain Graphs in Social Networks

社交网络平台的快速普及使得社交网络中的个人隐私泄露问题愈发受到用户的关心,传统的数据隐私保护方法无法满足用户数量巨大、关系复杂的社交网络隐私保护需求.图修改技术是针对社交网络数据的隐私保护所提出的一系列隐私保护措施,其中不确定图是将确定图转化为概率图的一种隐私保护方法.主要研究了不确定图中边概率赋值算法,提出了基于差分隐私的不确定图边概率赋值算法,该算法具有双重隐私保障,适合社交网络隐私保护要求高的场景.同时提出了基于三元闭包的不确定图边概率分配算法,该算法在实现隐私保护的同时保持了较高的数据效用,适合简单的社交网络隐私保护场景.分析与比较表明:与(k,ε)-混淆算法相比,基于差分隐私的不确定图边概率赋值算法可以实现较高的隐私保护效果,基于三元闭包的不确定图边概率分配算法具有较高的数据效用性.最后,为了衡量网络结构的失真程度,提出了基于网络结构熵的数据效用性度量算法,该算法能够度量不确定图与原始图结构的相似程度.

The rapid popularization of the social network platform is causing growing concern among users of personal privacy disclosure in social networks, and due to the characters of social network which have the large number of users and with complicated relationships, the traditional privacy preserving method cannot be applied to the social network privacy protection which have a number of users and complicated. Graph modification technique is a series of privacy preserving methods proposed for the privacy preserving of social network data. Uncertain graph is a privacy preserving method, which converting a deterministic graph into a probability graph. In this study, the edge probability assignment algorithm is mainly focused on in the uncertain graph, and an algorithm for assigning the edge probability assignment is proposed based on differential privacy. The algorithm has a double privacy protection, which is suitable for social networks with high privacy requirements. Meanwhile, a different algorithm of uncertain graphs’ edge probability assignment is presented based on the triadic closure, which achieves privacy preserve while maintains high data utility and suitable for simple social networks. The analysis and comparison show that the algorithm for assigning the edge probabilities of uncertain graph based on differential privacy can achieve a higher privacy preserving which was compared with obfuscation algorithm, and the algorithm of uncertain graphs’ edge probability assignment based on triadic closure has higher data utility. Finally, in order to measure the distortion of the network structure, a data utility measure is proposed based on network structure entropy. The algorithm can measure the similarity between the uncertain graph and the original structure.