吴振强,胡 静,田堉攀,史武超,颜 军

1(现代教学技术教育部重点实验室(陕西师范大学),陕西 西安 710062)

2(陕西师范大学 计算机科学学院,陕西 西安 710119)

1 引 言

随着互联网技术的日益成熟和快速普及,越来越多的用户通过社交网络平台进行沟通并共享信息,导致社交网络积累了大量的用户行为数据.这些数据中包含了大量的个人敏感信息,如身份信息、社会关系信息等,这些敏感信息容易引起不法分子的关注并成为安全攻击的目标.例如2016年5月19日,美国社交网站LinkedIn宣布,有一个叫“peace”的黑客组织在黑市上以 5比特币的售价公开销售 1.67亿个领英用户登录信息,其中有1.17亿包括电子邮件和密码;同年 6月初,同样是代号为“peace”的黑客称已经拿到了全球第二大的社交网站MySpace的3.6亿用户账号以及4.27亿密码,并且在暗网上以6个比特币的价格公开出售[1],使得用户的身心和财产安全遭到严重侵犯,除此之外,一些不法分子甚至利用这些账号信息在用户的亲友之间行骗.因此,如何在方便用户使用社交网络的同时,保护好用户的个人敏感信息不被泄露成为了急需解决的社会问题.

社交网络由多种角色构成,它们之间的关系错综复杂且相互影响.传统数据的隐私保护方法已经不适用于社交网络中的隐私信息保护,对社交网络的研究不仅要关注每个社会角色的属性,同时也要关注这些角色之间的关系.为了准确描述社交网络中实体之间的关系,可以将社交网络抽象成图(graph)结构,每个社会角色用节点表示,角色之间的关系通常用边来表示,角色之间关联程度可以通过对边进行加权重来表示[2].因此,对社交网络的研究可以转化为对图结构的研究.由于社交网络中包含许多个人的敏感信息,将其抽象为图结构后,图中的节点和边也会涉及到个人隐私信息,因此,通过研究图结构的隐私保护来实现社交网络隐私保护的目的.目前,社交网络隐私保护方法可分为 5类.(1) 标识符替换法.标识符替换是采用伪名的思想,用合成的标识符来替换掉身份证号或名字等唯一标识属性,这种方法实现简单但容易遭受背景信息攻击.Backstrom[3]等人提出在发布真实图数据之前用合成标识符替换可识别属性的隐私保护技术,但是这种方法容易受到背景知识的攻击,攻击者可以根据顶点的结构特征推断出顶点的身份信息.(2) 差分隐私法.差分隐私[4]是一种具有严格可证明的数学定义和可量化评估的隐私保护模型,将差分隐私应用到社交网络图结构中,可以提供一种严格、有效的量化评估方法.Hay等人[5]基于差分隐私技术提出图结构中节点和边差分隐私,其中边的差分隐私相对较为简单,因此应用更为广泛.Day等人[6]基于聚类和累积直方图提出了两种在节点差分隐私下发布度分布的方法.Karwa等人[7]提出了一种严格、高效的边差分隐私保护方法来发布实用性高的网络数据统计信息.Task等人[8]提出了图结构中出度差分隐私,实现简单,但相较于节点保护能力较弱.(3) 图聚类方法.图的聚类[9]是将多个节点或边聚合成一个超级节点集合,对外只公布超级节点的统计信息,从而保护了节点内用户的隐私.Hay等人[10]针对背景信息攻击提出一种基于节点聚类实现网络数据匿名化的隐私保护方法.考虑到社交网络中的关系对应图结构中的边,这些连接关系也会泄露个人隐私信息.Zheleva和Getoor[11]针对关系链识别攻击提出了一种基于边聚类的隐私保护方法.但聚类在一定程度上会降低原社交网络图数据的实用性,因此在满足隐私保护的前提下,为了尽可能地保持原图数据的实用性,引入边/顶点修改技术.(4) 边/顶点修改技术是对图的局部进行修改来实现隐私保护.针对社交网络中角色关系复杂多样的特点,可以通过随机修改图中部分边来实现社交网络图的匿名化,进而实现隐私保护的目的.随机边修改技术主要包括随机增添和删除边、随机旋转边和随机交换边3种.Ying等人[12]研究了不同的随机方法对于顶点之间关系的影响,提出了保护原始图特征谱的算法.攻击者依据原图中节点的度信息,仍可以重新定义原图数据信息.针对链接攻击,Liu和Terzi[13]提出了k-度匿名概念.k-度匿名模型是k-匿名[14]在图上的应用与拓展.设图G=(V,E)中的任意一个节点度数至少与k–1个节点的度数相同,则该图为k-度匿名图.(5) 不确定图方法.不确定图方法是向原社交网络图中的部分节点之间随机添加或删除小概率边来注入不确定性.通过对数据更小的扰动变化既可以实现隐私保护,又可以保持原数据效用性.2012年,Boldi等人[15]首次提出了(k,ε)-混淆算法,该方法在抗顶点身份攻击的同时保证了图结构数据的最小化失真;2013年,Mittal等人[16]提出了基于随机游走的不确定图数据发布方法,该方法可防止链接攻击;2014年,Nguyen等人[17]提出了方差最大化的方法来衡量隐私与效用之间的关系;2015年,Nguyen等人[18]在前期工作的基础上又提出了基于不确定邻接矩阵UAM的通用匿名模型,并将UAM引入到方差最大化算法中.为了提高不确定图方法的隐私保护效果,胡静[19]利用边差分隐私实现了对原图基于任何背景知识攻击的隐私保护,并且经过差分隐私的后置处理方法,提高了隐私保护的数据效用.

目前,不确定图已成为一种新的隐私保护方法,它的主要原理是将不确定性注入到社交网络图的边中,发布经混淆后的不确定图来达到隐私保护的目的.该方法通过为图中的边分配概率值来实现隐私保护,同时对原图数据改变较小,一定程度上保持了较高的原数据效用,相较于完全去除或添加边,保护效果更好.

本文针对社交网络图的隐私保护,提出了两种不确定图隐私保护算法:基于差分隐私的不确定图边概率赋值算法和基于三元闭包的不确定图边概率分配算法.为了对现有算法和本文提出的算法进行统一的隐私分析,我们采用边熵来衡量算法的隐私保护程度.同时,针对社交网络的度量问题,提出了一种基于网络结构熵的图结构数据效用性的度量算法,该算法与k度匿名模型相比,能够更加精确地反映出网络结构隐私性的变化过程.

本文第1节介绍背景和相关工作.第2节介绍本文算法的相关基础知识.第3节基于不确定图中边概率的赋值提出两种社交网络图隐私保护算法:基于差分隐私的不确定图边概率赋值算法和三元闭包的不确定图边概率分配算法.第 4节对本文提出的两种算法分别从数据的隐私性和效用性方面进行实验验证分析.第 5节提出一种基于网络结构熵的图结构数据效用性度量算法.第6节总结全文并展望下一步工作.

2 相关基础知识

2.1 差分隐私的基本定义和相关概念

定义1(差分隐私).存在两个相邻数据集D,D′和算法K,K(D)表示算法K在数据集D上的输出集合,O是算法K所有输出值的集合,若算法K在数据集D和D′上任意输出结果为满足下面不等式(1):

则算法K满足ε-差分隐私.ε称为隐私保护预算,ε的取值决定了保护效果,ε取值的大小与保护效果成正比,与数据失真程度成反比.差分隐私以其严格的数学定义为隐私的评价提供了理论依据.

差分隐私实现机制包括:指数机制、拉普拉斯机制和高斯机制.其中,指数机制一般应用于非数值类数据,拉普拉斯机制和高斯机制适用于数值型数据的隐私保护.

定义2(邻近图).给定图G1=(V1,E1),G2=(V2,E2),若在G1,G2中有 |V1⊕V2|+ |E1⊕E2|= 1 ,则称G1、G2为邻近图.

本文中,由于V1=V2,只要 |E1⊕E2|= 1 ,即E1与E2的汉明距离为 1,我们就称G1、G2为邻近图,如图 1所示,图1(a)和图1(b)所示为邻近图.

Fig.1 The example of neighboring graphs图1 邻近图示例

定义3(敏感度).给定一个函数f:G→G″,其中,G、G′具有相同的顶点集合,函数f的全局敏感度为

其中,G1、G2是邻近图,G″为经过随机算法后的输出图,f是查询函数,表示对于G1、G2中的边ei,查询边ei是否存在于G1和G2中,图 1(a)和图 1(b)中的Δf=2.

定义4(边差分隐私).给定一种随机算法M,Range(M)为算法M的取值范围,若算法M在邻近图G1、G2上的输出结果S(S∈Range(M))满足:

则称算法M满足ε-差分隐私,其中,ε表示隐私保护程度,Pr[.]表示算法M的随机性.

为了实现边差分隐私,通过拉普拉斯分布产生的噪声值加入到真实输出值实现边数据的扰动,从而实现了差分隐私保护.

定义5(Laplace机制).对于函数f:G→G′,若算法M的输出结果满足下列等式,则称算法M是满足ε-差分隐私的.

其中,Lap(Δf/ε)是添加到查询结果中的期望值为0,位置参数是Δf/ε的拉普拉斯分布的噪声.同时,噪声值的大小与敏感度Δf和隐私预算ε有关.这种通过添加服从拉普拉斯的噪声值实现差分隐私的机制称为Laplace机制.

2.2 不确定图

定义 6(不确定图).给定一个图G=(V,E),如果映射p:Vp→[0,1]是边集中每条边存在的概率函数,那么图G′=(V,p)是关于图G的不确定图,其中,Vp表示集合V中所有可能的顶点对,即Vp={(vi,vj)|1≤i

2.3 三元闭包

定义 7(邻近潜在边). Leskovec等人[20]指出,真实图中节点之间的链接概率随着它们层级之间相对距离的增加而减小,这些边的存在可以减少基于最短路径的统计.Vázquez[21]提出最近邻居可以解释邻居间的聚集系数、平均度和度分布的能量规律,这些属性与对社交网络图的观察结果完全一致.

三元闭包的基本原则:如果两个人有共同的朋友,这两个人将来成为朋友的可能性就会增加.例如,节点B和节点C具有共同的朋友A,则B和C成为朋友的概率会增加.类似地,节点A和节点E之间也会产生关联边,如图 2所示.将三元闭包理论引入到社交网络研究中,可以形成三角形网络结构,利用三角形结构特性将原图转变为不确定图.

Fig.2 The theory of triadic closure图2 三元闭包理论模型

2.4 网络结构熵

熵表示系统的混乱程度.网络结构熵是对整个网络结构是否有序的度量.网络结构熵Entropy定义如下:

其中,di为节点vi的度.当网络结构为全连接图时,其值最大,反之,无边相连的孤立节点图,其值最小.

2.5k-度匿名

k-度匿名模型是k-匿名在图上的应用与拓展,由Liu等人[13]首次提出,相关概念定义如下.

(1)k-匿名向量.如果一个向量中的每个值在该向量中出现的次数至少是k次,则这个向量被称作k-匿名向量.例如向量v=[4,4,3,3,3],则该向量为2-匿名向量.

(2)k-度匿名图.G=(V,E)表示一个图,如果这个图的度序列所组成的向量是一个k-匿名向量,则该图为k-度匿名图.

3 基于不确定图的隐私保护算法

本节主要介绍两种基于不确定图边概率赋值的隐私保护算法,并分别对其给出详细介绍.基于差分隐私的不确定图边概率赋值算法(简称差分隐私法)提供了严格可证明的隐私保护,并在一定程度上保护了数据效用.基于三元闭包的不确定图边概率分配算法(简称三元闭包法)不仅实现了隐私保护的目的,而且有约束的分配边概率可以保持较高的数据效用.

3.1 差分隐私法

下面首先将不确定图的构造过程抽象为一个模型,然后在该模型下提出一种基于差分隐私技术实现不确定图边概率赋值的隐私保护(uncertain graph based on differential privacy,简称UGDP)模型,并对该模型进行说明.然后给出UGDP算法的伪代码并进行分析.最后,证明了UGDP算法满足差分隐私.

1) 不确定图模型

Fig.3 Uncertain graph construction model of UGDP algrothm图3 UGDP算法的不确定图构造模型

该模型(如图3所示)包括3个部分,第1部分和第3部分为算法的输入和输出,其中,算法的输入为原始数据图,输出为不确定图,中间部分是该模型的主要环节,研究者可以根据不同的需求提出不同的隐私保护算法来实现不确定图的隐私保护.在该模型下,我们提出了基于差分隐私的不确定图边概率赋值算法UGDP.

2) UGDP算法

UGDP算法是利用差分隐私技术来实现不确定图边概率赋值的隐私保护算法,算法的执行框如图 4所示,主要由以下4步组成.

Fig.4 The UGDP algorithm图4 UGDP算法

(1) 利用 Laplace机制进行加噪,产生的噪声表示为Y=(y1,y2,…,yi,…,yN),将产生的噪声加入图G1或G2中,得到噪声图.

(2) 为了构造不确定图,每个噪声值yi对应一个概率值pi,概率值pi=Pr[yi]=F(yi).

(3) 将概率值pi加入到图G1或G2中构成不确定图,将概率值pi作为顶点和顶点之间存在边的概率.

其中,g(x)是服从期望值μ、位置参数b的拉普拉斯分布.

(4) 在进行数据发布时,为了更好地保护图中的隐私信息,将邻近不确定G′作为发布图.

算法详细描述如算法1所示.

算法1.UGDP算法.

定理.UGDP算法满足差分隐私.

证明:令f(.)为函数f:G→G″,G″是算法输出的不确定图,G1、G2为邻近图即图中边的汉明距离为1.PG1表示UGDP(G1,f,ε)的概率密度函数,PG2表示UGDP(G2,f,ε)的概率密度函数.概率和噪声的关系为yi～pi.G3是算法过程中得到的噪声图.因为噪声图到不确定图的过程符合差分隐私的后置处理技术,因此为了证明 UGDP算法满足差分隐私,只需要证明原图到噪声图的过程满足差分隐私即可.具体证明过程如下.

由于UGDP算法是在符合不确定图隐私的同时满足差分隐私,具有双重的隐私保护效果,因此,UGDP算法具有较强的隐私保护的特征.在隐私性度量上我们采取差分隐私的度量方式,即用隐私预算ε来度量隐私保护程度.隐私预算ε越小,噪声的取值范围越广,噪声值对应的概率的取值也越广,在边混淆时达到的混淆程度越好,因此隐私保护效果越好.反之,隐私预算ε越大,噪声的取值范围越窄,噪声值对应的概率的取值也越窄,在边混淆时达到的混淆程度较差,因此隐私保护效果较差.

本文提出的 UGDP算法与原有的不确定图算法相比,在满足不确定图的同时满足差分隐私的所有特征,尤其它是一种严格可证明的隐私保护算法,然而,该算法也存在某些局限性,如数据的低可用性问题.

3.2 三元闭包法

本节首先构建不确定图模型,并在该模型下提出一种基于三元闭包的不确定图边概率分配算法来实现图的匿名化,然后对该模型的 3个主要流程详细描述并给出该算法的伪代码.该算法在实现隐私保护的同时保持了原数据的效用性.

1) 基于三元闭包的不确定图算法模型

如图5所示,该模型包括5个部分,第1部分和第5部分为算法的输入和输出,其中,算法的输入为原始数据图,输出为不确定图,中间部分是该模型的主要环节,该环节分为3个步骤,具体内容详见后续的算法描述.

Fig.5 Uncertain graph based on triadic closure algorithm图5 基于三元闭包的不确定图构造模型

2) 算法描述

对于一个社交网络图G,它的点集为V,边集为E.

(1) 加边

该过程(如图6所示)首先集中在收集图中所需的信息以获得节点集V和一个边集E.我们随机选择点u,v∈V且边(u,v)∉E,若两点之间的距离dis(u,v)等于2,则将边(u,v)加到图G中.如图6所示,最多可以增加3条边.

Fig.6 Add-edges图6 加边

(2) 确定三角形数量

当添加边(u,v)时,这个边与其附近的两个邻近边可以形成一个三角形,继续执行上一步,可以得到多个三角形.为了得到需要的三角形,在选择三角形时必须附加一些约束条件.如果两个三角形具有公共边,必须选择一个并放弃一个.最终得到一个三角形集合,该集合中任意两个三角形没有公共边.例如,在图7中,当添加边AE和边BE时,得到ΔAED和ΔBEC.然后判断两个三角形是否具有公共边.如图7所示,这两个三角形没有公共边,则可以将边AE和边BE添加到图中.与边AE和边BE相反,边CD被放弃,因为包括边AE的ΔAED与ΔDEC具有相同边ED.

Fig.7 Determine the triangle图7 确定三角形数量

详细的描述如算法2和算法3所示.

算法2.加边和选取三角形.

算法3.注入不确定.

(3) 注入不确定性

对三角形集合中每个三角形的3条边随机分配概率,为了使原图的边概率保持不变,本文规定每个三角形3条边的概率和,且原图中不属于三角形的边的概率值为 1.通过向所有边注入概率值,可以将原图转换为不确定图.当所有的边完成概率赋值后,可以得到,E等于原图中边的个数.通过对边注入不G确定性生成的不确定图如图8所示.

Fig.8 Injecting probability图8 注入不确定性

通过上述流程,我们在增加约束的条件下对原图G注入不确定性,得到不确定图G′.

3) 算法分析

为了实现较高的隐私保护效果,将原图转换为不确定图,则攻击者按组合方法只能以比较低的概率从不确定图中恢复出原图,因此本算法能够实现对原图的概率性保护.在基于三元闭包的不确定图边概率分配算法中,首先基于三元闭包原理对原图加边,实现对原图的修改.然后,选择加边形成的三角形,对其三边分配一定的概率值得到一个不确定图.若具有概率值的三角形越多,则能够得到原图的概率越低,因此该算法能够对原图进行隐私保护.在转换过程中,对于三角形的概率分配进行限制,使得三边的概率之和等于 2,目的是确保加边前后的边概率之和保持不变.在这种约束条件下,得到的不确定图的边数概率之和等于原图的边数概率之和.同时,这种约束条件可以提高不确定图的数据效用.因此,基于三元闭包的不确定图算法既能实现隐私保护,又保持了较高的数据效用性.

提出的基于三元闭包的不确定图边概率分配算法,通过加边构建三角形集合并对选择后的三角形集合中所有的边注入不确定性,将原社交网络图转化为不确定图,进而实现对社交网络的隐私保护.该算法在对社交网络隐私保护的同时保持了原网络数据效用,与其他已有算法相比,在处理简单的社交网络数据时,该算法运行效率更高.由于该算法是对网络图的局部进行扰动,所以对于更复杂的网络图还需要进一步加以探索.

4 分析与比较

为了对不同隐私保护方法的隐私效果进行评价,下面利用不确定图的边概率信息,引入边熵来衡量所发布不确定图的隐私保护程度,并以此为评价依据衡量变换前后隐私程度的变化情况.同时,为了验证算法对数据的效用性影响程度,又定义了一些图统计指标来说明本文算法的数据效用性.然后,利用Python语言及第三方功能包 NetworkX对本文算法进行程序编程和仿真实验.实验数据分为两部分,一部分为真实数据集,一部分为合成数据集.真实数据集来自于Karate和Dolphin俱乐部,合成数据集分别为200和500个节点,连接概率为0.2的随机网络图.为了减少随机性,实验进行了10次模拟取平均值.

4.1 隐私性度量

信息熵是信息论中用于度量信息量的一个概念,一个系统越是有序,信息熵就越低;反之,一个系统越是混乱,信息熵就越高,在不确定图隐私度量中,由于不确定图的边具有很强的随机性,我们引入边熵Ente来衡量隐私保护效果.根据边的不确定程度,使用边熵来衡量不确定图的不确定性,即不确定图对原始图的隐私保护程度,不确定图的边熵定义如以下公式所示.

其中,ei∈G′,p(ei)是该条边存在的概率.

其中,Ente为不确定图的边熵,Ente值越大,表示不确定图的不确定程度越大,对应隐私保护方法的隐私保护效果越好.

4.2 数据效用性度量

根据文献[15,18]中提出的相关指标来度量算法的数据效用性,其中,NE表示图中边的个数,AD表示图中节点的平均度,DV表示图中节点的度方差.

在图数据中,我们用d1,d2,…,dn来表示图中节点度的序列.由于不确定图中每条边是以概率的形式出现的,因此我们不能直接用确定图中节点的度来表示不确定图中节点的度.在不确定图中,节点度的序列d1,d2,…,dn是一些随机变量.我们利用节点的期望度来表示不确定图中节点的度,也就是说,对于任意的节点v∈V,节点v的期望度是与它相连的边的概率之和,见等式(11).

在公式(11)中我们规定i=v或者j=v且i≠j.

原始图中NE、AD的计算见公式(12)、公式(13),不确定图中NE′、AD′的计算见公式(15)、公式(16),其中,DV在原始图与不确定图中的计算方式一致,见公式(14).

4.3 隐私性分析

为了对本文所提出的方法和已有方法的隐私性进行统一度量,我们利用边熵的变化情况来说明隐私保护效果.表1为UGDP算法边熵的变化情况,表2为三元闭包法中边熵的变化情况,表3为(k,ε)-混淆算法中边熵的变化情况.

边熵是用来度量图的不确定性程度,边熵的值越大表明图的不确定程度越大.表1表示的是UGDP算法中边熵的变化情况,随着节点个数的增加,边熵也对应增大,表明整个图的不确定程度在加大,即隐私保护效果越好.由于 UGDP算法是符合差分隐私的,根据差分隐私的特性可知,隐私预算ε越小,则隐私保护程度越高.但是,在利用UGDP算法将确定图转化为不确定图时,边概率的赋值服从拉普拉斯分布,具有一定的随机性,因此,边熵的变化也具有随机性,与差分隐私的隐私保护程度不一定完全相符,也就是说,隐私预算越小,边熵的值不一定越大.

Table 1 The changes of edge-entropy in UGDP algorithm表1 UGDP算法中边熵的变化情况

基于三元闭包的不确定图边概率分配算法在生成不确定图的过程中,对原图进行加边,然后对选择后的三角形的边赋予概率值.在表 2中,随着边数的增加,得到的不确定图的边熵也在增加,表现为同步增长趋势.这种趋势反映了图隐私保护的效果越来越好,同时证明了三元闭包法能够实现隐私保护的目的m为不确定图的生成过程中总共添加的边数,c为调节加边数的因子,实际添加的边数为m.c.

Table 2 The changes of edge-entropy in triadic closure algorithm表2 三元闭包法中边熵的变化情况

(k,ε)-混淆算法将确定图转化为不确定图时可以保持较好的数据效用性[18],为了把该算法达到的隐私保护效果与本文提出的算法进行直观的对比,下面采用边熵来进行隐私性度量.表 3为(k,ε)-混淆算法中边熵的变化情况,由于篇幅和不同参数组合具有的多种可能性,下面只列出(k,ε)-混淆算法的一种情形来说明隐私保护效果,同时隐私度量的主要参数即混淆级别k的取值分别为10和20,其他参数分别为ε=0.1,c=1,q=0.01.

Table 3 The changes of edge-entropy in (k,ε)-obfuscation algorithm表3 (k,ε)-混淆算法中边熵的变化情况

通过表1和表3的对比,如果利用边熵来度量算法的隐私性,则UGDP算法在隐私保护程度上优于(k,ε)-混淆算法,可以达到较好的隐私保护效果.通过表2和表3的对比,(k,ε)-混淆算法优于三元闭包方法,可以达到较好的隐私保护效果.

4.4 数据效用性分析

在隐私保护的同时,我们通过NE、AD、DV对数据效用性进行了测量,见表4～表7.表4和表5列出UGDP算法的数据效用性.在表4中,对原始数据图的数据效用及ε=0.1时UGDP算法生成的不确定图的数据效用进行了对比,可以看出,UGDP算法的数据效用性较低.同时,表 5表示的是不同隐私预算ε下的数据效用性的对比,我们得出隐私预算ε越大,隐私保护程度越差,数据效用性相对较好的结论.

表6列出的是三元闭包法的数据效用性.在表6中,通过三元闭包法得到的不确定图与原图比较可以得出,在度量指标NE、AD中,数据效用性保持不变,这说明,通过该方法得到的不确定图具有较好的数据效用性.同时,DV在网络中明显增加,这说明,对原图进行修改时节点的度发生了变化.

Table 4 Comparison of data utility between uncertain graphs generated by UGDP algorithm whenε=0.1 and original graph表4 原始图与ε=0.1时UGDP生成的不确定图的数据效用性比较

Table 5 Comparison of data utility whenε=0.01 andε=1 in uncertain graphs generated by UGDP algorithm表5ε=0.01与ε=1时UGDP算法生成的不确定图的数据效用性比较

Table 6 Comparison of data utility between uncertain graphs generated by triadic closure algorithm and original graph表6 原始图与三元闭包法生成的不确定图的数据效用性比较

表7列出了不同k值情况下(k,ε)-混淆算法的数据效用性.通过度量指标NE、AD、DV在原始图和不确定图中的对比,我们可以看出,该算法具有较好的数据效用性.

Table 7 Data utility comparison for differentk values in (k,ε)-obfuscation algorithm表7 (k,ε)-混淆算法中不同k值的数据效用性对比

通过不同算法的数据效用性比较,我们可以得出以下结论:UGDP算法的数据效用性较差,三元闭包法的数据效用性最好,(k,ε)-混淆算法的数据效用性介于这两种算法之间.

4.5 算法整体分析

数据的隐私性与效用性本身是一对矛盾体,如果要达到高的隐私保护程度,通常就需要牺牲数据的效用性.在第4.3节和第4.4节中通过与现有的(k,ε)-混淆算法进行对比可以看出,本文提出的UGDP算法具有较高的隐私保护性,但是这种高隐私保护程度是通过牺牲数据的效用性而得到的.同时,三元闭包方法具有高数据效用性,然而该方法的隐私保护性偏低.

不同的场景可能需要不同的需求,若需要达到高隐私保护程度或者高数据效用性,则可以根据不同的需求来选择不同的隐私保护算法.

5 基于网络结构熵的度量算法

本节首先介绍网络结构熵可作为隐私度量的评价依据来度量图的隐私性,其次使用网络结构熵来衡量不确定图算法对原始图的破坏程度.

5.1 网络结构熵的隐私性度量

相关匿名算法[22]提出对隐私进行量化可以检验隐私保护算法的优劣,因此对图结构的隐私进行度量具有重要的理论意义和应用价值.网络结构熵是对整个结构是否有序的度量,自然可以用于研究图结构隐私度量..根据k度匿名图模型,图9(a)和图9(b)都是1度匿名图,图9(c)是2度匿

如图 9所示,4个节点的连通网络结构的节点间连接方式不同,它们的度序列向量分别是名图,图9(d)是4度匿名图.毫无疑问,图9(d)达到最高匿名级别,图9(c)达到中等匿名级别,图9(a)和图9(b)达到相同匿名级别但具有不同的结构.可以看出,从1度匿名到2度匿名存在一个逐渐变化的过程,但k度匿名图模型并不能准确地反映出这个变化过程.

Fig.9 Four kinds of graphs with the same nodes but different linking relationships图9 4种具有相同节点但不同链接关系的图结构

k-度匿名图模型的核心思想是度序列向量的匿名性.在一个k匿名向量中,在没有任何辅助信息的前提下,任何一个元素被识别出来的概率不超过1/k.因此,许多图修改算法都通过加减边或者节点的方法来使图的度序列分布得更加均匀,而网络静态特征是用来描述网络特征的微观数量分布统计或宏观数量平均值统计.为了更加细致地描绘度序列的变化过程,本文采取网络静态特征之一的网络结构熵作为隐私度量指标来度量图的隐私性变化情况.

度序列分布反映了图的“形状”信息,而熵反映了图的“形状”是否有规律.图的形状越有规则,随机性就越小,因此熵就越小;若熵越大,图的度序列分布也越均匀.根据式(5)和式(6),在k邻近图中网络熵取最大值Entroymax=log2n,在星型图中其取得最小值Entropymin=log24(n–1)/2,其中,n表示图中所有节点的个数.

在图 9(a)到图9(d)的网络结构熵依次为 1.242、1.321、1.366和1.386.因此,隐私程度越高,网络结构熵越大.尽管图9(a)和图9(b)在k-度匿名下的隐私程度相同,但网络结构熵仍然可以区分这两个不同结构的隐私变化.

5.2 图结构数据效用性度量算法

网络结构熵的变化还可以用来衡量网络结构的变化,在衡量不确定图算法对原始图结构的破坏程度时,我们提出了基于网络结构熵的数据效用性度量算法.利用该算法可以判断原始图和不确定图结构熵的变化情况,从而可以衡量图结构的失真程度.不确定图的结构熵与原始图的结构熵越接近,说明不确定图对原始图的改变程度较小,较好地保持了原图的数据效用性.

结构熵是衡量网络结构的重要指标,可以精确、简洁地度量复杂网络的非同质性,当网络受损分裂成几个随机网或者多数节点在非连通的情况下,网络结构熵会变小.从表 8中我们可以看出,原始图的结构熵与经过差分隐私法及三元闭包算法得到的不确定图的结构熵的差值不大,且不确定图中的网络结构熵相对于原始网络图来说较小,两者之间的误差值固定在0.2之内.表8只列出了节点个数小于等于500时网络结构熵的变化情况.随着节点个数的增加,两者网络结构熵的差值在逐渐减小.这说明,本文的算法在大数据场景下很好地保持了网络的结构特性.因此,与原始图的结构熵相比,4种数据集在不同算法下得到的不确定图的结构熵与原始图的结构熵基本保持不变,从而说明我们提出的不确定图算法可以很好地保持原始图的结构特征.

详细描述如算法4所示.

算法4.图结构数据效用性度量算法.

Table 8 The changes of network structure-entropy表8 网络结构熵的变化情况

6 结 论

本文基于不确定图方法针对社交网络隐私保护提出两种不确定图算法:基于差分隐私的不确定图边概率赋值算法和基于三元闭包的不确定图边概率分配算法.差分隐私法将差分隐私与不确定图结合,不仅符合不确定图隐私保护方法,同时具有差分隐私的严格可证明特征,可以达到双重隐私保证,但其数据效用性有待提高.三元闭包法将三元闭包理论与不确定图结合实现了社交网络隐私保护,并在一定程度上保持了较高的数据效用,与(k,ε)-混淆算法相比,在处理简单的社交网络图数据时运行效率更高.因此,在下一步工作中,我们将探索三元闭包法在大规模社交网络图中的实证研究.同时,根据网络结构熵的特征,提出了一种基于网络结构熵的数据效用性度量算法,用来衡量对原始图结构的破坏程度,对于这方面内容的内在机理是未来重点探索的内容.