DP2Gsister:差分隐私社交网络图发布模型*

殷轶平，徐睿峰

(1.哈尔滨工业大学深圳研究生院 计算机科学与技术学院，广东 深圳 518055；2.哈尔滨工程大学 国家保密学院，黑龙江 哈尔滨 150001)

0 引言

近年来，以Twitter、Facebook、微博为代表的在线社交网络得到飞速发展。由于可以实时获取海量真实用户的用户属性、个人表达、交互关系等内容，社交网络被广泛用于用户建模、社区发现、信息推荐等应用和研究。例如Facebook作为全球最受欢迎的在线社交网络之一，拥有大量的好友关系信息，可以被用来分析社群关系，挖掘社会观点。然而，一些存在的关系可能被用户视为敏感信息，直接发布会导致个人信息的严重泄露。2018年3月16日，美国纽约时报曝光Facebook超过5000万用户的个人信息数据被泄露并被用于选举干预等非法行为。这一事件突显出社交媒体数据的滥用可能带来的严重后果，为数据持有者敲响了警钟。因此，在发布社交媒体数据之前，必须对其进行处理，使数据在具有隐私保证的基础上支持相关的研究工作。

因此，考虑到社交网络数据的紧密关联性，本文研究将注意力放在添加尽可能少的噪声来实现图数据的差分隐私保护。为此，本文提出了一种非交互式的严格差分隐私方法，称为DP2Gsister(Two- phase Differential Privacy for Gsister)。这一方法的主要思想是分两个阶段实现差分隐私以形成与原图结构信息相似且具有隐私保证的发布图Gsister。第一阶段引入层次随机图模型重构图结构特征，用满足ε1-差分隐私的MCMC在原图上采集样本Tsample；第二阶段计算Tsample的连接概率，对其添加隐私预算为ε2的拉普拉斯噪声以生成概率噪声序列{Pn}；然后按照概率序列生成发布图Gsister。对于给定的社交网络数据集，本研究的目标是:(1)实现单次发布和增量发布社交网络图的边差分隐私；(2)尽可能地保留原始社交网络图的结构信息。

本文的主要贡献如下：

(1)研究了不直接对边进行扰动的边差分隐私方法，通过满足差分隐私约束的MCMC算法先采样HRG的树状图，再对HRG内部的连接概率进行干扰来实现差分隐私。

(2)研究了一种可用于社交网络图发布的差分隐私保护模型DP2Gsister，其包括DPtoTsample和DPtoGsister两个主要算法。

(3)设计了一种扩展的DP2Gsister方法，称为multiR_DP2Gsister，可以用于增量图发布中的隐私保护。

(4)在真实数据集上进行实验，从算法收敛性、度分布、信息损失度、平均聚类系数、平均路径长度几方面做评估与分析，证明本文研究的模型在保证数据隐私性的基础上较好地保证了数据可用性[11]。

1 相关概念及背景知识

本文主要研究面向无向无权社交网络[12]的差分隐私保护方法。首先介绍与本文研究相关的概念及背景知识。

1.1 主要符号及其意义

本文中主要符号及其意义如表1所示。

1.2 差分隐私

定义1：ε-差分隐私

一个随机算法Α的输出空间为Range(A)。若对任意一对邻居数据集D,D′和D和D′有且只有一条记录k不同，及任一输出O∈Range(A)均满足：

Pk[A(D)∈O]≤eεPk[A(D′)∈O]

则称算法Α满足ε-差分隐私[5]，ε为隐私预算，P表示概率。差分隐私隐藏了单个个体在数据集中的存在性。ε越小，隐私保证越强。

定义2：全局敏感度

对于任意一对邻居数据集D和D′，查询函数f的全局敏感度定义为：

(2)

定义3：拉普拉斯机制

DWORK C等人[5]首次提出拉普拉斯机制，对于一个数据集D，一个函数f，一个隐私参数ε，函数f的返回值是真实值加噪声后的结果。这个噪声是由概率密度函数为

(3)

的拉普拉斯分布产生的。对于任意的函数f：D→R，算法A(D)=f(D)+满足ε-差分隐私。

定义4：指数机制

定义一个估价函数q，它对每一种输出计算出一个分值，分值高的输出有更大概率被发布。

1.3 层次随机图模型(HRG)[13]

定义4：层次随机图模型是基于节点间关联程度构建的二叉树结构的随机图模型。对于一个图G，HRG通过其树状结构T和连接概率序列{Pr}来表征G。如图1所示，图1(a)表示社交网络图G，图1(b)和图1(c)分别表示它对应的两个可能的树状结构。内部节点r标记的数值为以该节点为根节点的左右子树的连接概率Pr，Pr=|er|/(|nLr|·|nRr|)，其中，er为左右子树之间的连接数，nLr和nRr分别为左右子树中的节点数量。

图1 层次随机图模型

1.4 似然函数L

似然函数L为

(4)

1.5 姊妹图

本文提出“姊妹图”的概念，用Gsister表示。姊妹图是一系列差分隐私算法处理后得到的发布图，它尽可能好地保留了原始图的结构信息。

2 DP2Gsister：基于差分隐私的社交网络数据发布模型

利用HRG模型进行社交网络数据发布隐私保护模型研究时需要应对两个挑战：(1)使HRG尽可能近似地保留原始社交网络图的结构信息；(2)实现边差分隐私以保护网络中个体之间的关系。

为此，本文设计了DP2Gsister模型。该模型分成两个阶段来应对上述挑战：(1)算法1，利用MCMC算法差分隐私的从所有原图可能生成的候选树状图空间T中采集样本图Tsample；(2)算法2，对于Tsample中的连接概率序列{Pr}应用拉普拉斯机制添加噪声生成噪声概率序列{Pn}.根据Tsample和{Pn}生成净化后的社交网络图Gsister。将全部的隐私预算ε分为ε1和ε2两部分，分别用于算法1和算法2，使其均满足差分隐私。

2.1 差分隐私算法设计

算法1为差分隐私MCMC算法,下面给出具体的算法步骤，如表2所示。

算法2为差分隐私姊妹图生成算法，下面给出具体的算法步骤，如表3所示。

表2 差分隐私MCMC算法

表3 差分隐私姊妹图生成算法

算法2的主要思路是计算层次随机图的内部节点的连接概率，进而利用拉普拉斯机制对其添加噪声。由定义3可知算法满足ε2-边差分隐私。最后按照内部节点的噪声概率序列依次生成相对应的边，从而得到发布的姊妹图Gsister。

根据差分隐私的组合特性可知，DP2Gsister模型满足ε-差分隐私，其中ε=ε1+ε2。

2.2 multiR_DP2Gsister：增量社交网络图发布隐私保护模型

由上述算法1和算法2构成的DP2Gsister模型适用于单次数据发布场景下的隐私保护。然而，考虑到真实的社交网络是不断变化的，将针对单次数据发布的方法直接应用到多次数据发布的场景下效果不佳。因此，为解决增量数据发布的隐私保护问题，在DP2Gsister模型的基础上研究设计了一种可用于增量社交网络图发布的隐私保护算法，称为multiR_DP2Gsister。

① http://socialnetworks.mpi-sws.org/data-wosn2009.html

② http://snap.stanford.edu/data/index.html

定义:随时间增量变化的社交网络图表示为G1，G2，…，Gt，时刻t的社交网络图表示为Gt=。假设Gt相对于Gt-1“只增不减”，即Vt-1∈Vt，Et-1∈Et。本研究只考虑边的增添，忽略节点的变化。

由于社交网络中的节点具有很强的关联性，节点间一条边的增加就有可能改变样本树状图的整个结构。高敏感性直接造成了需要添加的噪声增多。因此，针对层次随机图的高敏感特征，在DP2Gsister的基础上，本文设计了用于实现增量社交网络图发布的隐私保护模型multiR_DP2Gsister，下面给出具体的算法步骤，如表4所示。

表4 差分隐私增量社交网络图发布算法

算法3的主要思想是利用t1时刻的样本层次随机图编码网络结构，对于每一条新增的边，找到其对应的叶子节点的最小共同祖先rlowest，更新rlowest的连接概率，进而添加拉普拉斯噪声使其满足ε2′-差分隐私。样本层次随机图的树状结构Tsample是隐私预算设为0.5时DPtoTsample采样得到的。

此外，在添加噪声之前，增设一项策略判断噪声尺度是否超过某个阈值，若超出阈值，则认为添加这样的噪声会严重破坏网络结构。解决方法是当噪声尺度λ超出设定的范围时，用Erdos-Renyi随机图模型置换当前对应的子树，然后再添加噪声进行扰动。

3 实验评估及分析

为了评估DP2Gsister和multiR_DP2Gsister模型的可用性，本文在两个典型的社交网络数据集(Facebook①和wiki-Vote②)上进行了实验。实验环境为Intel Corei5 CPU 3.20 GHz，8 G内存，Ubuntu服务器，编程语言C++。

3.1 实验设置

实验分别选用静态数据集(统计信息见表5)和增量数据集(统计信息见表6)评估DP2Gsister和multiR_DP2Gsister两个模型的效果。

表5 静态数据集统计信息

表5中数据集Facebook包含的是朋友关系信息，节点代表Facebook用户，如Facebook中包含13 097位用户；边代表用户之间的朋友关系，某用户与另一位用户是Facebook好友，则边数计1，相应的代表两位用户的节点之间产生一条连接，此数据集中包含44 624条边。Wikipedia是由世界各地的志愿者合作撰写的免费百科全书。数据集wiki-Vote包含的是维基百科管理员的选举投票信息，其中节点代表参与选举投票的维基百科用户，该数据集包含7 115位用户；边代表用户之间的投票关系，某用户为另一位用户投票，则边数计1，该数据集包含100 762条边。

表6 增量数据集统计信息

表6中数据集Facebook1包含的是2007年1月至2007年6月Facebook网络中的朋友关系信息，数据集Facebook2包含的是2007年7月时Facebook网络中的朋友关系信息，包含14 561位用户，58 331条边，此时相对于数据集Facebook1新增了13 707条边，即新增13 707条朋友关系记录。因为本研究只考虑边的增删，不考虑节点的改变，所以在实验前首先对数据集Facebook2进行处理，删除与数据集Facebook1相比新增节点关联的边，只保留在原始节点间新增的边。

3.2 实验评估与分析

在实验中，首先从算法收敛性、度分布两方面对DP2Gsister模型进行实验评估与分析，然后从信息损失度、平均聚类系数、平均路径长度三方面对multiR_DP2Gsister模型进行实验评估与分析。

3.2.1DP2Gsister模型的实验评估与分析

将DP2Gsister模型的隐私预算设为ε=1(ε=ε1+ε2)，分成ε1=0.5 和ε2=0.5，ε1=0.2 和ε2=0.8，ε1=0.8 和ε2=0.2三种组合，在表1所示数据集上进行实验并分析结果。

(1)logL-step

如图2所示，实验通过分析log-likelihood随马尔科夫步数step的变化趋势判断MCMC算法的收敛情况。图2(a)和图2(b)分别展示了在Facebook和wiki-Vote数据集上，不同预算分配下logL随马尔科夫步数step的变化趋势。可以发现logL随着step的增加逐渐变大且很快趋于稳定，说明DP2Gsister在MCMC运行下采样图与原始图的相似度越来越高且收敛很快。此外，可以观察到ε1=0.5和ε2=0.8的效果差距不大，由此可以推断即使分配较少的隐私预算也不会影响数据可用性。

图2 MCMC算法收敛情况

(2)度分布

如图3所示，实验通过对比原始社交网络图G和发布图Gsister的度分布统计情况分析发布数据的可用性。图3(a)和图3(b)分别展示了Facebook和wiki-Vote的原始图和发布图的度分布统计情况。图中横轴表示度数，纵轴表示拥有相应度数的节点数。original对应的曲线代表原始图的度分布情况，其余三条曲线分别代表ε1=0.5和ε2=0.5，ε1=0.2和ε2=0.8，ε1=0.8和ε2=0.2三组隐私预算分配下得到的发布图的度分布情况。可以发现DP2Gsister在三组实验中均能使发布图保持和原始图相似的度分布，表现为大多数节点拥有低度数，极少节点拥有高度数的网络特征。这证明该模型能够很好地保留原始图的结构特点，从而保证数据可用。

图3 度分布情况

3.2.2multiR_DP2Gsister模型的实验评估与分析

上述实验证明DP2Gsister模型在处理单次数据发布上效果显著，接下来实验评估其扩展模型multiR_DP2Gsister的效果。设置multiR_DP2Gsister模型的隐私预算为ε2′=0.5，在图2所示的数据集上进行实验并分析结果。

(1)信息损失度

要实现增量数据发布中的隐私保护，往往需要添加更多的噪声以保证与单次发布时相仿的数据质量。额外添加的噪声容易导致数据损失增加，因此，分析隐私保护模型处理后的数据损失是衡量模型效果的一项重要指标。本文引入信息损失度(Information Loss, IL)衡量数据可用性。

信息损失度为:

(5)

图4所示为t=1和t=2时刻经multiR_DP2Gsister模型处理后的发布图的信息损失度量。从图中可以看出，对于t=2时刻增加了边的数据集，该算法将信息损失控制在25%以下较好地保证了数据可用性。

图4 t1和t2时刻发布图的信息损失

(2)平均聚类系数和平均最短路径

平均聚类系数(Average Clustering Coefficient, ACC)和平均最短路径(Average Path Length, APL)通常被用来衡量网络的整体特征。因此，本文引入ACC和APL衡量原始图和发布图的特征差异。

(6)

其中，Ci为节点i的局部聚类系数，T(i)为网络中由节点i参与组成的三角形的数目，d(i)为节点i的度数。

(7)

其中，n为网络中的节点数目，PL(i,j)为节点i、j之间的最短路径。

如表3所示，用平均聚类系数ACC和平均路径长度APL量化原始图和发布图的网络特征，可以看出multiR_DP2Gsister模型处理后的发布图在APL上与原始图差异非常小，在ACC上差异不大，证明发布图能够较好地保留原始的网络特征。

表3 multiR_DP2Gsister处理后的发布图与原始图ACC和APL对比情况

4 结论

本文在社交网络数据发布的场景下研究了一种差分隐私社交网络图发布模型DP2Gsister。该模型利用差分隐私MCMC算法DPtoTsample和差分隐私姊妹图生成算法DPtoGsister重构原始图的结构信息，进而对连接概率添加噪声，最终生成具有隐私保证的姊妹图Gsister，且实验证明Gsister较好地保留了原始图的结构信息。此外，考虑社交网络数据增量更新的需求，对DP2Gsister进行扩展得到multiR-DP2Gsister模型，该模型可用于增量社交网络图发布的隐私保护。实验证明本文研究的模型在数据可用性与隐私性之间达到了较好的平衡。

[1] CHENG J, FU W C, LIU J. K-isomorphism: privacy preserving network publication against structural attacks[C]// ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June. DBLP, 2010:459-470.

[2] SUN C, YU P S, KONG X, et al. Privacy preserving social network publication against mutual friend attacks[C]//International Conference on Data Mining Workshops. IEEE, 2013:883-890.

[3] ZHOU B, PEI J. Preserving privacy in social networks against neighborhood attacks[C]//International Conference on Data Engineering. IEEE, 2008:506-515．

[4] 郭彩华, 王斌, 朱怀杰,等. 增量的动态社会网络匿名化技术[J]. 计算机研究与发展, 2016, 53(6):1352-1364.

[5] DWORK C, MCSHERRY F, NISSIM K. Calibrating noise to sensitivity in private data analysis[J]. Lecture Notes in Computer Science, 2006, 3876(8):265-284.

[6] CHEN R, FUNG B C M, YU P S, et al. Correlated network data publication via differential privacy[J]. VLDB Journal — the International Journal on Very Large Data Bases, 2014, 23(4):653-676.

[7] ZHANG X, MENG X, CHEN R. Differentially private set-valued data release against incremental updates[M].Database Systems for Advanced Applications, 2013:392-406.

[8] XIAO Q, CHEN R, TAN K L. Differentially private network data release via structural inference[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2014:911-920.

[9] WANG Y, WU X, WU L. Differential privacy preserving spectral graph analysis[C]// Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 2013:329-340.

[10] DWORK C. The differential privacy frontier (extended abstract)[J]. Theory of Cryptography Conference, 2009, 5444:496-502.

[11] FUNG B C M, WANG K, CHEN R, et al. Privacy-preserving data publishing: a survey of recent developments[J]. ACM Computing Surveys, 2010, 42(4):14.

[12] 刘向宇, 王斌, 杨晓春. 社会网络数据发布隐私保护技术综述[J]. 软件学报, 2014, 25(3):576-590.

[13] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008, 453(7191):98.