基于Skyline计算的社交网络关系数据隐私保护

张书旋 康海燕 闫涵

摘 要：随着社交软件的流行，越来越多的人加入社交网络产生了大量有价值的信息，其中也包含了许多敏感隐私信息。不同的用户有不同的隐私需求，因此需要不同级别的隐私保护。社交网络中用户隐私泄露等级受社交网络图结构和用户自身威胁等级等诸多因素的影响。针对社交网络数据的个性化隐私保护问题及用户隐私泄露等级评价问题，提出基于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 引言

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

差分隐私[1]被公认是一个强大的隐私保护模型，能够为数据提供强大的隐私保证，但是该模型局限于为所有个人提供相同级别的隐私保护; 然而并非所有用户都需要相同的隐私级别，为避免对那些不需要太高隐私级别的用户提供过多的隐私保护，需要实现个性化的隐私保护。本文采用采样方法实现个性化差分隐私保护，引入非均匀的不确定性。

采样机制以前为其他目的已经与差分隐私结合过。Li等[2]提出了一种满足差分隐私的扰动方法，利用采样的随机性降低隐私成本，证明了均匀随机采样提高了差分隐私保护效果。Kellaris等 [3]提出了GS预处理方法（preprocesses by Grouping and Smoothing， GS），利用抽样机制对发布数据进行分组，降低拉普拉斯噪声注入并实现差分隐私。Spiessl等[4]設计了一个根据灵敏度采样的采样器，能自动实现（ε，δ，γ）随机差分隐私。

Skyline計算的研究分两方面：一是对Skyline计算算法的优化，二是将Skyline计算算法应用于相关研究领域。目前， 数据的海量性和高维性以及数据环境的多样性和动态性都使 Skyline计算面临着愈加严峻的挑战。各国学者针对这个问题进行了不少研究， 主要得出以下几种Skyline计算算法：块嵌套算法[5]、最近邻算法[6]、分支界限算法[7]等。Skyline算法在多标准决策系统、城市导航系统、数据库可视化、用户偏好查询等多个研究领域都有着广泛应用， 例如： 在传感器网络应用中，信俊昌等[8]提出了基于过滤的Skyline节点连续查询算法（FIlterbased Skyline node moniToring algorithm， FIST），FIST算法能有效减少Skyline节点连续查询过程中传感器节点的通信代价，进而降低传感器网络的能量消耗; 多维向量查询方面，雷婷等[9]在云环境下提出一种基于超球面投影分区的 Skyline算法，通过将空间坐标投影到超球面上转化为超球面投影坐标，然后使用超球面投影坐标进行分区，有效提高分区内数据点的平均减枝力度，降低 Skyline 的计算代价; 在用户偏好查询方面，Zhang等[10]提出了一种使用Skyline查询的算法，通过用户的搜索和查询，以确定哪种云服务最能满足用户的需求。本文利用Skyline计算方法给用户评定隐私泄露等级，然后根据用户隐私泄露等级进行采样处理，最后添加噪声实现个性化的差分隐私保护。

本文的主要贡献包括：1）利用采样方法实现个性化差分隐私，引入非均匀的不确定性; 2）构建了用户属性向量，利用Skyline计算方法给用户评定隐私泄露等级; 3）提出了基于基于Skyline计算的个性化差分隐私保护（Personalized Differential Privacy based on Skyline， PDPS）算法发布机制的总体流程， 对数据采集、数据处理、数据分析和数据发布各个流程进行了阐述说明; 4）在真实数据集上与传统个性化差分隐私（Personalized Differential Privacy， PDP）算法进行对比，验证了发布数据安全性和可用性的提升。

4 结语

本文针对社交网络用户隐私泄露等级评定和差分隐私保护的个性化这两个问题，提出PDPS算法用来发布社交网络关系数据。将Skyline计算用于用户隐私泄露等级的评定，并用采样机制来实现了个性化的差分隐私保护。在真实数据集上对该算法的隐私保护效果和数据的效用进行了验证，证明了PDPS算法能够提升社交网络数据发布的安全性和可用性。今后可对分割和采样系数的选取规则、带权重的社交网络图的发布算法等方向进行下一步研究。

参考文献 （References）

[1] 王豪，徐正全.面向轨迹聚类的差分隐私保护方法[J]. 华中科技大学学报（自然科学版）， 2018， 46（1）：32-36. （WANG H， XU Z Q. Differential privacy preserving method for trajectory clustering[J]. Journal of Huazhong University of Science & Technology （Natural Science Edition）， 2018， 46（1）：32-36.）

[2] LI N， QARDAJI W， DONG S. On sampling， anonymization， and differential privacy or， kanonymization meets differential privacy[C]// Proceedings of the 2012 ACM Symposium on Information， Computer and Communications Security. New York： ACM， 2012：32-33.

[3] KELLARIS G， PAPADOPOULOS S. Practical differential privacy via grouping and smoothing[J]. Proceedings of the VLDB Endowment， 2013， 6（5）：301-312.

[4] SPIESSL S M， BECKER D A. Sensitivity analysis of a final repository model with quasidiscrete behaviour using quasirandom sampling and a metamodel approach in comparison to other variancebased techniques[J]. Reliability Engineering & System Safety， 2015， 134：287-296.

[5] SARMA A D， LALL A， NANONGKAI D， et al. Randomized multipass streaming Skyline algorithms[J]. Proceedings of the VLDB Endowment， 2009， 2（1）：85-96.

[6] KANJ S， ABDALLAH F， DENEUX T， et al. Editing training data for multilabel classification with the knearest neighbor rule[J]. Pattern Analysis & Applications， 2016， 19（1）：145-161.

[7] ZHENG J， CHEN J， WANG H. Efficient geometric pruning strategies for continuous Skyline queries[J]. ISPRS International Journal of GeoInformation， 2017， 6（3）：91.

[8] 信俊昌， 王国仁. 无线传感器网络中Skyline节点连续查询算法[J]. 计算机学报， 2012， 35（11）： 2415-2430.（XIN J C， WANG G R. Continuous Skyline nodes query processing over wireless sensor networks[J].Chinese Journal of Computers， 2012， 35（11）：2415-2430.）

[9] 雷婷，王涛，曲武，等.云环境下基于超球面投影分区的Skyline计算[J].计算机科学，2013，40（6）：164-171. （LEI T， WANG T， QU W， et al. Distributed Skyline processing based on hypersphere projection partitioning on cloud environments[J]. Computer Science， 2013， 40（6）： 164-171.）

[10] ZHANG B， ZHOU S， GUAN J. Adapting Skyline computation to the MapReduce framework： algorithms and experiments[C]// Proceedings of the 16th International Conference on Database Systems for Advanced Applications. Berlin： SpringerVerlag， 2011：403-414.

[11] GULZAR Y， ALWAN A A， SALLEH N， et al. A model for Skyline query processing in a partially complete database[J]. Advanced Science Letters， 2018， 24（2）：400-407.

[12] 康海燕， 馬跃雷. 差分隐私保护在数据挖掘中应用综述[J]. 山东大学学报（理学版）， 2017， 52（3）：16-23.（KANG H Y， MA Y L. Survey on application of data mining via differential privacy[J]. Journal of Shandong University （Natural Science）， 2017， 52（3）：16-23.）

[13] JORGENSEN Z， YU T， CORMODE G. Conservative or liberal？ Personalized differential privacy[C]// Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. Piscataway， NJ： IEEE， 2015：1023-1034.

[14] WANG Y， ZHENG B. Preserving privacy in social networks against connection fingerprint attacks[C]// Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. Piscataway， NJ： IEEE， 2015：54-65.