| 摘要: |
| 社交网络平台的快速普及使得社交网络中的个人隐私泄露问题愈发受到用户的关心，传统的数据隐私保护方法无法满足用户数量巨大、关系复杂的社交网络隐私保护需求.图修改技术是针对社交网络数据的隐私保护所提出的一系列隐私保护措施，其中不确定图是将确定图转化为概率图的一种隐私保护方法.主要研究了不确定图中边概率赋值算法，提出了基于差分隐私的不确定图边概率赋值算法，该算法具有双重隐私保障，适合社交网络隐私保护要求高的场景.同时提出了基于三元闭包的不确定图边概率分配算法，该算法在实现隐私保护的同时保持了较高的数据效用，适合简单的社交网络隐私保护场景.分析与比较表明：与（k，ε）-混淆算法相比，基于差分隐私的不确定图边概率赋值算法可以实现较高的隐私保护效果，基于三元闭包的不确定图边概率分配算法具有较高的数据效用性.最后，为了衡量网络结构的失真程度，提出了基于网络结构熵的数据效用性度量算法，该算法能够度量不确定图与原始图结构的相似程度. |
| 关键词: 社交网络 不确定图 差分隐私 三元闭包 网络结构熵 |
| DOI：10.13328/j.cnki.jos.005368 |
| 分类号: |
| 基金项目:国家自然科学基金（61602290，61173190）；中央高校基本科研业务费专项资金（GK201704017，GK201501008） |
|
| Privacy Preserving Algorithms of Uncertain Graphs in Social Networks |
|
WU Zhen-Qiang1,2, HU Jing2, TIAN Yu-Pan2, SHI Wu-Chao2, YAN Jun2
|
|
1.Key Laboratory of Modern Teching Technology of Ministry of Education(Shaanxi Normal University), Xi'an 710062, China;2.School of Computer Science, Shaanxi Normal University, Xi'an 710119, China
|
| Abstract: |
| 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. |
| Key words: social network uncertain graph differential privacy triadic closure network structure entropy |
