社会网络数据发布隐私保护技术综述

　　摘要:对社会网络隐私保护的研究现状与进展进行了阐述.首先介绍了社会网络隐私保护问题的研究背景,进而从社会网络中的隐私、攻击者背景知识、社会网络数据隐私保护技术、数据可用性与实验测评等方面对当前研究工作进行了细致的分类归纳和分析,指出了当前社会网络隐私保护的不足以及不同隐私保护技术间的对比和优缺点,并对未来需要深入研究的方向进行了展望.对社会网络数据隐私保护研究的主流方法和前沿进展进行了概括、比较和分析.

　　关键词:社会网络;隐私保护;数据发布

　　随着网络技术以及社交网站的迅速发展,例如Facebook、MySpace、人人网等,通过社交网站进行交友、联系和互动的用户群体数量迅速增加.以Facebook为例,其用户总数在2013年1月突破10亿,约占世界人口的14%.由于社会网络的繁荣和广泛应用,越来越多的研究学者和开发人员将其科学研究和应用开发的注意力集中到社会网络这种虚拟世界当中.社会网络分析已经成为社会学、地理学、经济学、信息学等诸多学科的研究热点.

　　基于社会网络数据进行数据挖掘和分析潜在模式比传统关系数据更加科学、效果更好,社会网络分析又称为链接挖掘(linkmining).通过对社会网络进行链接挖掘可以获得实体更丰富(如某实体在整个网络中的重要性)、更准确(如预测某实体所属类别)的信息.因此,亟待发布和共享更多的社会网络数据,为数据挖掘和模式分析提供更丰富的数据来源.然而,发布和共享社会网络数据会导致隐私泄露,并且社会网络中的隐私信息类型广泛,潜在隐私泄露方式更加多样化.例如:在电话网络中,Ada和Bob之间频繁的电话和短信联系可能被视为敏感关系,因为他们不希望别人得知他们之间的亲密关系;在医疗网络中,某人与肺癌医生之间的联系可能被其视为敏感信息.大量研究工作为关系数据提供隐私保护,其中,文献首先提出K-匿名隐私保护模型,继而出现了一系列基于K-匿名模型的关系数据隐私保护技术.但是,关系数据隐私保护技术不能为社会网络数据提供隐私保护,这是因为关系数据隐私保护模型仅考虑攻击者将关系数据中每条记录的属性值作为背景知识进行隐私攻击,忽略了社会网络中结点之间的关系、社会网络图结构、结点在图中的结构和位置重要性等均可作为攻击者的背景知识进行隐私攻击.文献基于真实数据,通过实验证明了社会网络面临很大的隐私攻击和泄露的威胁.可以看出,关系数据只是社会网络数据中结点之间相互独立时的特例,因此,关系数据隐私保护技术不能够满足社会网络数据的隐私保护要求,需要基于社会网络数据的特点研究相应的数据隐私保护技术.本文对近年来社会网络数据隐私保护研究工作进行了归纳总结,指出了当前社会网络隐私保护的不足以及不同隐私保护技术间的对比和优缺点.

　　1、社会网络中的隐私信息

　　在社会网络中,组成社会网络的各个元素均可能涉及到隐私信息,包括结点、边、图性质等.在本文中,社会网络隐私分类为结点隐私、边隐私、图性质隐私。1.1社会网络中的结点隐私

　　在社会网络中,每个结点代表了社会中的真实个体,而与结点相关的任何信息均有可能成为隐私.本文将结点隐私具体分类为结点存在性、结点再识别、结点属性值、结点图结构等隐私信息.

　　（1）结点存在性

　　所谓结点存在性,是指某个人是否以结点的形式出现在某个社会网络中.在某些情况下,某些人会将自己出现在某特定社会网络视为隐私信息.如果某人将此视为隐私信息,发布数据时应防止攻击者结合背景知识推测出该人存在此社会网络中.例如,传染病传播网络对于研究公共健康和疾病传播途径等方面具有很大价值,然而在发布传染病传播网络数据的同时,如果攻击者能够推断出某攻击目标存在于此传染病传播网络中,则导致了该攻击目标隐私信息的泄露.从表1中可以看出,目前针对保护结点存在性隐私信息的研究工作尚属空白.

　　（2）结点再识别

　　在发布社会网络数据时,为了保护网络中实体的隐私信息,通常将所有结点的身份信息删除,使得攻击者不能识别和推测出攻击目标在社会网络中的准确位置.但是攻击者可以基于与攻击目标相关的背景知识对社会网络中的结点进行匹配识别,从而准确地或者以一定概率识别攻击目标在社会网络中的位置.在社会网络中,攻击者基于背景知识对攻击目标的位置进行匹配识别的过程称为结点再识别.

　　（3）结点属性值

　　社会网络中的每个结点具有属性值,这些属性值描述了社会中每个人的真实信息,其中某些属性信息会涉及到个人隐私,例如收入信息、医疗记录中的患病信息等.发布社会网络数据时,结点之间的相互关系使得攻击者具有更多的背景知识推测目标结点的敏感属性信息.例如在家族遗传病史社会网络中,即使删除了某个重要结点的疾病信息,但是攻击者还可以基于其亲戚患有遗传疾病的情况,推测该目标结点可能患有的疾病.文献提出采用结点K-匿名的方法来保护结点的敏感属性值,而文献显示了基于社会网络基本常识即可准确地推测出大部分结点的敏感属性信息.

　　（4）结点图结构

　　不仅结点的某些属性值是敏感的,结点在社会网络中的图结构性质在某些情况下也被视为敏感和隐私,例如结点的度、两个结点间的最短距离、结点到社会网络中某个社区中心的距离等.例如在商品供货网络中,每个结点的入度和出度分别表示其供货渠道数目和销售渠道的数目,这些信息属于需要保护的敏感信息而防止其被竞争对手获得.所示了目前尚无相关工作针对保护结点的图结构隐私信息进行深入研究.

　　1.2社会网络中的边隐私

　　在社会网络中,一条边表示其两端结点具有某种关系,结点由于相互间具有各种关系从而形成庞大的网络图.在某些情况下,边相关信息可能是敏感的,例如两点之间是否具有某种关系、参与某种敏感关系的结点信息、边权重、边的相关属性等.本文将边隐私具体分类为边存在性、边再识别、边权重、边属性值等隐私信息.

　　（1）边存在性

　　所谓边存在性,是指社会网络中的两个指定结点是否具有某种关系.如果某两个结点的边是敏感的,简单地将此两个目标结点的敏感边删除并不能很好地保护隐私信息,攻击者可以通过背景知识推测两个目标结点是否具有敏感边.文献假设攻击者采用noisy-or概率模型并基于现有结点之间的边连接来计算目标结点间具有敏感关系的概率,从而对可能被删除的敏感边进行恢复.在文献中,通过实验验证了在真实社会网络数据上采用链接推演技术可以高概率地预测两个目标结点之间是否具有边连接.

　　（2）边再识别

　　对于社会网络中的某条边,识别该边两端结点的过程称为边再识别.在社会网络中,每条边的两端连接着社会网络中的两个结点,表明两个结点所代表的个人具有某种关系,该关系可能被视为敏感信息.例如在异性交友网络中,两个结点之间的边表示了两个结点所代表的个人曾经具有男女朋友关系,显然,此种关系可能涉及个人隐私.文献研究了如何使边再识别概率小于指定阈值.文献同样将两结点之间的边连接视为隐私信息,并提出技术保证在不得知结点之间边连接情况的同时,较准确地计算任意两点之间的最短路径长度.

　　（3）边权重

　　在不同应用背景中,社会网络中的边具有权重.在电子邮件通信网络中,边权重可以表示两个人之间收发电子邮件数目;在商业网络中,边权重可以表示两个商业公司之间的贸易额.类似商业公司之间的贸易额等边权重信息可能被视为敏感信息.在文献中,研究了在防止边权重值泄露的同时保持某些重要结点间的最短路径不变;而文献提出的技术在对边权重提供隐私保护的同时保证线性图性质不变.

　　（4）边属性值

　　与结点属性值相似,社会网络中的边也可以具有属性值,例如边上的标签可以表示边两端结点的关系类型.边的敏感属性值对于边的两端结点所代表的个人来说属于隐私信息.文献研究了在社会网络中,如何防止攻击者基于背景知识推测出边的敏感属性值.

　　1.3社会网络中的图性质隐私

　　很多图性质是社会网络分析的重要评估标准,例如中间性(结点位于其他结点连接路径上的度)、中心性(结点与其他结点具有关系的数目)、路径长度(网络中两结点间的最短距离)、可达性(任意结点与其他结点联通的度)等.某些结点的图性质亦被视为个人隐私信息,目前尚无相关工作对结点图性质提供隐私保护.

　　对社会网络中的隐私信息进行分类归纳意义重大,因为社会网络中,不同类型隐私信息泄露均会威胁到个人隐私信息安全,只有对社会网络中的隐私信息做好辨识和分类工作,才能对不同隐私信息提出相应保护技术.,社会网络中很多方面的隐私信息需要深入研究来为其提供保护.

　　2、攻击者背景知识

　　由于社会网络蕴含的信息具有多样化的特点,攻击者可以采用多种类型知识发动隐私攻击,对进行社会网络隐私保护提出很大挑战.本文将攻击者背景知识分类为社会网络图结构、结点信息、边信息、预测模型等方面。

　　2.1社会网络图结构

　　攻击者可以将结点间连接情况,即社会网络图结构,作为背景知识来进行隐私攻击.社会网络图结构可具体分类为结点邻居图、社会网络子图、图查询等方面,为攻击者提供图结构背景知识.

　　（1）结点邻居图

　　在社会网络中,将距离结点u长度d之内的所有结点称为u的d-邻居结点,u的d-邻居结点及其相互之间的边构成的子图称为结点u的d-邻居子图.结点邻居图是一种常见的图结构背景知识.

　　（2）子图

　　在社会网络图中,攻击者可以将具有特殊连接模式的子图作为背景知识,从而为其进行隐私攻击提供结构唯一性的识别标记.

　　文献针对结构唯一性子图导致隐私泄露的可行性进行了研究:在发布社会网络数据前,攻击者嵌入具有结构唯一性的子图,并建立该子图与目标结点之间的连接,当匿名化的社会网络数据发布后,攻击者首先识别嵌入子图,然后基于嵌入子图和目标结点之间的联系来识别目标结点.通过实验显示,嵌入由7个结点构建的特殊子图平均可以识别出70个目标结点.

　　（3）图查询

　　在社会网络中可以执行多种图查询,而针对某些结点或者边的图查询结果具有唯一性,从而为攻击者提供了进行隐私攻击的背景知识.

　　例如:对于结点v,定义查询Q(v)为v的所有邻居结点度的升序序列.Q(Fred)=[2,2,4].如果攻击者将Fred的朋友的度信息作为背景知识,则可以在中识别出结点5即是Fred,因为只有结点5的度序列与Fred相同.文献评估了不同图查询作为背景知识的隐私攻击能力;而文献虽然没有定义可导致隐私泄露的图查询,但其提供的隐私保护技术可以防御部分或者全部图查询导致的隐私泄露.

　　2.2结点信息

　　对于某些社会网络隐私攻击,尤其是结点隐私攻击,攻击者会将结点自身的一些相关信息作为背景知识.

　　（1）结点属性值

　　社会网络中结点的属性值可以分类为标识属性和敏感属性.标识属性为攻击者提供了结点识别的背景知识,例如年龄、性别、籍贯、学历等,攻击者可以将网络中的结点标识属性值和其掌握的实体属性值进行链接匹配,从而识别结点的真实身份.文献研究了如何防范基于结点属性值的结点再识别隐私攻击,而文献侧重研究攻击者基于结点属性值进行边再识别隐私攻击.

　　（2）结点度

　　在社会网络中,结点度表示了该结点所代表的实体与社会中的其他实体之间的关系数目,在现实中,攻击者很容易收集到目标的度信息,并作为背景知识进行结点再识别、边再识别等隐私攻击.

　　描述了如何基于结点度进行结点再识别攻击.只有结点A的度为2,其他结点的度均为1,因此,当攻击者掌握A的度为2的背景知识时,可以很容易地识别出A在社会网络中的位置.相似地,攻击者可以基于目标结点的度进行边再识别攻击.在文献中,假设攻击者背景知识为互为邻居的两个结点的度,结点C,D的度对(1,1).由于中具有度对(1,1)的边只有一条,所以攻击者识别出边CD的成功概率为100%.

　　2.3边信息

　　社会网络中,连接结点的边是其重要的组成部分,攻击者可以将边的相关信息作为背景知识,包括边连接关、边属性值等.

　　（1）连接关系

　　如果攻击者事先掌握了某些目标的边连接关系,则可以根据这些连接关系进行推演,从而获得隐私信息.文献[17,18,23]研究了连接关系可能导致的隐私泄露.参照表示基于连接关系的隐私攻击的图3,如果朋友关系被视为敏感关系,则可以基于图3(a)中u1和u2与结点friend1的连接关系推断出u1和u2具有朋友关系的隐私信息.

　　（2）边属性值

　　边上的属性值(标签、权重等)可以为攻击者提供隐私攻击的背景知识.例如在朋友网络中,边标签表示朋友之间的联系方式,可以是电话、短信、电子邮件等.如果攻击者知道某目标基本上仅采用电子邮件与其他朋友联系,基于此背景知识,攻击者能够以很大概率在社会网络中识别出这个目标结点.在加权社会网络图中,边权重可以作为攻击者的背景知识.文献研究了加权图中目标结点与其他结点相连接的边权重信息如何导致身份泄露.对于结点v,将与v相连接的边权重按照降序排序得到的序列定义为结点v的权重包,记作wv.例如,结点A权重包为wA=[wAB,wAD]=[2,1].如果攻击者掌握了结点A的权重包信息,则可以识别出中的结点1即为A,从而导致了身份泄露.

　　2.4预测模型

　　攻击者可以基于社会网络常识构建预测模型,从而推演目标的隐私信息.当前,社会网络中的预测模型主要分为两类:基于邻居的预测模型和基于兴趣组的预测模型.

　　（1）基于邻居的预测模型

　　所谓物以类聚,人以群分,在社会网络中,此种现象尤为明显.一般情况下,具有朋友关系的实体具有相同或相似的属性值,攻击者可以根据邻居属性值来推断目标的敏感属性值.在文献中,研究了采用贝叶斯网络来推演目标的敏感属性值.相似地,可以通过链接推演技术来预测和恢复社会网络中的敏感关系.很多链接推演技术均是基于社会人际交往常识,其中一项常识是:如果两个人具有很多共同朋友,则他们也很有可能是朋友.文献评估了在真实数据集Email-1和LiveJ-1上采用链接推演技术预测敏感关系的可行性.在实验测试中,如果两个结点的共同邻居数目大于阈值.,则认为两者在图中具有边连接.实验结果表明:当.增大时,正确预测率逐渐增高;当.=20时,Email-1和LiveJ-1数据集上的正确预测率分别达到了91.06%和66.5%.可以看出:攻击者可以凭借链接推演技术,以较高的概率推断出社会网络中的敏感关系.

　　在社会网络中,结点之间具有不同的关系.基于常识可以知道,各种关系之间不是相互独立而是相关的.例如,具有同学关系的两个人是朋友的概率比没有任何关系的两个人是朋友的概率大.在文献中,研究了通过非敏感关系边采用noisy-or概率预测模型来预测敏感关系.seij=1表示结点i和j具有敏感关系s,如果边ek(k=1,…,n)的影响参数是.k,ek对于seij的影响是相互独立的,并且所有观察边对于seij的影响参数是.0,则基于noisy-or概率模型得到结点i和j具有敏感关系s的概率为1。

　　（2）基于兴趣组的预测模型

　　在社会网络中,实体加入不同的兴趣组,比如在豆瓣网中,每个用户可以凭借自己爱好加入诸如摄影、影视等方面的兴趣组.利用实体之间的朋友关系、加入兴趣组情况,可以对实体的隐私属性进行推测.其基本思想是:参加相同兴趣组的两个实体具有相同属性值的概率较大;参加相同兴趣组的数目越多,则两个实体具有相同属性值的概率越大.

　　在文献中,基于实体参加兴趣组的情况,采用贝叶斯法则来推测未知属性值.由于每个兴趣组中组员属性值分布不同,即每个兴趣组对属性值的预测能力不同,文献提出了兴趣组细化的贝叶斯分类器,可以较高概率地预测未知属性值.在文献中提出的预测模型中,不仅考虑了实体参与兴趣组情况,也结合了实体之间的朋友关系,其属性值预测准确率高于文献中的预测模型.

　　3、社会网络数据隐私保护技术

　　针对不同背景知识可能导致的隐私泄露,提出了相应的社会网络隐私保护技术.本节分别从隐私保护方法、动态性、并行性等方面介绍当前社会网络隐私保护技术,并指出不同隐私保护技术的优缺点.

　　3.1隐私保护方法

　　社会网络隐私保护方法主要分为结点K-匿名、子图K-匿名、数据扰乱、推演控制这4种.

　　结点K-匿名和子图K-匿名的主要思想是:攻击者基于目标背景知识在匿名化社会网络数据中进行匹配识别时,至少有K个候选符合,即目标的隐私泄露概率小于1/K;.数据扰乱的主要思想是:对社会网络进行随机化修改,使得攻击者不能准确地推测出原始真实数据,数据扰乱方法具体分为数值扰乱和图结构扰乱;.推演控制的主要思想是:对于不同隐私预测模型,通过对社会网络进行针对性地修改,使得攻击者采用预测模型不能推演出隐私信息,从而起到保护社会网络隐私的目的.

　　3.1.1结点K-匿名

　　所谓结点K-匿名,是指通过将社会网络中所有结点聚类成若干超点,其中每个超点至少包含K个结点,由于在超点中结点相互之间不可区分,因此在该社会网络中,受结点再识别攻击而导致隐私泄露的概率小于1/K.

　　显然,结点聚类成超点导致了边两端结点的信息损失,增加了图结构不确定性,降低了数据可用性.假设匿名图G的超点集为V,则G的可能社会网络数目W(G)可以通过公式(2)计算得到,其中,d(X,X)表示超点X内的边数目,d(X,Y)表示超点X和Y之间的边数目.在文献中,研究如何通过结点聚类实现结点K-匿名的同时最小化|W(G)|,其提出的技术主要基于模拟退火思想.文献在文献基础上做了改进,与文献中研究简单社会网络不同,文献假设社会网络中的每个结点具有属性信息,通过结点聚类生成超点时,每个超点内所有结点的属性信息还需要进行匿名化处理使得属性值相等,因此不仅会造成图结构信息损失,也会造成结点属性值的信息损失.文献提出一种贪心聚类方法来实现复杂社会网络的结点K-匿名.由于文献提出的匿名算法需要数据发布者通过设定权重来决定图匿名过程侧重于减少图结构信息损失还是结点属性信息损失,而两者的数据可用性难以量化,使得在实际应用中无法设定所需的权重,导致文献中方法的实用性较差.文献采用结点K-匿名来隐藏二部图社会网络中的敏感关系.进行结点K-匿名化后的二部图社会网络数据.结点K-匿名隐私保护能力强,具有很好的通用性,可以防止多种类型隐私泄露.然而,结点K-匿名在提供强隐私保护的同时,导致了图数据可用性降低,并且结点K-匿名的执行效率低,不适用于大型社会网络数据.