张书旋 康海燕 闫涵

摘 要：随着社交软件的流行，越来越多的人加入社交网络产生了大量有价值的信息，其中也包含了许多敏感隐私信息。不同的用户有不同的隐私需求，因此需要不同级别的隐私保护。社交网络中用户隐私泄露等级受社交网络图结构和用户自身威胁等级等诸多因素的影响。针对社交网络数据的个性化隐私保护问题及用户隐私泄露等级评价问题，提出基于Skyline计算的个性化差分隐私保护策略（PDPS）用以发布社交网络关系数据。首先构建用户的属性向量; 接着采用基于Skyline计算的方法评定用户的隐私泄露等级，并根据该等级对用户数据集进行分割;然后应用采样机制来实现个性化差分隐私，并对整合后的数据添加噪声;最后对处理后数据进行安全性和实用性的分析并发布数据。在真实数据集上与传统的个性化差分隐私方法（PDP）对比，验证了PDPS算法的隐私保护质量和数据的可用性都优于PDP算法。

关键词：社交网络;隐私保护;Skyline计算;个性化差分隐私;基于Skyline计算的个性化差分隐私保护算法

中图分类号：TP309

文献标志码：A

Abstract： With the popularity and development of social software， more and more people join the social network， which produces a lot of valuable information， including sensitive private information. Different users have different private requirements and therefore require different levels of privacy protection. The level of user privacy leak in social network is affected by many factors， such as the structure of social network graph and the threat level of the user himself. Aiming at the personalized differential privacy preserving problem and user privacy leak level problem， a Personalized Differential Privacy based on Skyline （PDPS） algorithm was proposed to publish social network relational data. Firstly， users attribute vector was built. Secondly， the user privacy leak level was calculated by Skyline computation method and the user dataset was segmented according to this level. Thirdly， with the sampling mechanism， the users with different privacy requirements were protected at different levels to realize personalized differential privacy and noise was added to the integreted data. Finally， the processed data were analyzed for security and availability and published. The experimental results demonstrate that compared with the traditional Personalized Differential Privacy （PDP） method on the real data set， PDPS algorithm has better privacy protection quality and data availability.

英文关键词Key words： social network; privacy preserving; Skyline query; personalized differential privacy; Personalized Differential Privacy based on Skyline （PDPS） algorithm

0 引言

社交网络隐私信息可以分为两种：一种隐私是用户敏感信息隐私，比如用户的手机号码、家庭住址、疾病、收入等;另一种隐私是社交网络关系隐私，即社交网络中人与人之间的连接关系信息，如亲属关系、同学关系。在社交网络中无论是哪种类型隐私信息的披露都可能会使个人的隐私受到威胁， 因此，隐私信息的识别和分类是非常必要的，需结合具体的信息类别来采取相应有效的保护策略。……