论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　社会网络隐私保护方法主要分为结点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-匿名的执行效率低,不适用于大型社会网络数据.

　　3.1.2子图K-匿名

　　所谓子图K-匿名,是指当攻击者将目标所在的特定子图作为背景知识进行隐私攻击时,社会网络中至少有个子图可作为候选,则目标子图导致隐私泄露的概率小于1/K.与目标相关的标识性子图均可作为攻击者的背景知识,例如结点的度、邻居图等.通过在社会网络中加伪点、加伪边、删除边、概括等,可实现子图K-匿名.

　　文献研究了攻击者将结点的度作为背景知识时如何进行子图K-匿名,提出了采用K-度匿名图来防止此类攻击.所谓K-度匿名图,是指对于该图中的任意结点,至少有K.1个结点与该点的度相同.例如,文献通过采用动态规划的方法实现了通过加入最少数目的边来生成K-度匿名图.在文献中,每个结点可以设定所需的隐私保护级别:第1级别为防止结点标签导致身份泄露;第2级别为防止结点标签、度导致身份泄露;第3级别为防止结点标签、度、结点边标签导致身份泄露.对于需要第2级别和第3级别隐私保护的结点,文献对其进行K-度匿名化操作.文献在生成K-度匿名图的同时,最小化社团结构信息损失.由于攻击者能够获得比结点度更复杂的目标子图背景知识,因此K-度匿名的隐私保护能力较差.

　　当攻击者将目标的1-邻居图作为背景知识时,文献提出的匿名化方法使得对于任意结点的1-邻居图,至少有K.1个结点的1-邻居图与其同构.在匿名过程中,需要加入伪边和概括结点标签.可以看出:具有唯一邻居图的结点6在匿名后与结点2和结点9具有相同的邻居图,因此攻击者基于结点6的1-邻居图获得其真实身份的概率小于1/2.为了防范攻击者将任意目标子图作为背景知识,文献提出将社会网络匿名化为K-对称图.所谓K-对称图,是指对于图中的任意结点v,在图中至少存在K.1个结点与v是结构对等的.例如,其中添加的伪点v3.与v3结构对等,因此攻击者识别出v3的真实身份概率为1/2.显然,为了构建K-对称图,匿名化时需要在社会网络数据中加入伪点和伪边.K-对称图的潜在隐私威胁是:当攻击者获知K-对称图生成算法时,可以将发布的K-对称图中结构对等的结点进行合并,还原出部分原始图,从而导致隐私泄露.文献提出K-自同构来进行隐私保护.所谓K-自同构,是指图自身存在着K个同构映射.K-自同构能够阻止结点再识别隐私攻击,但是不能防范敏感关系隐私攻击.为了能够同时保护结点和边隐私,文献提出K-同构隐私保护模型.所谓K-同构,是指社会网络图分为K个子图,子图之间相互同构.为了实现K-同构,首先需要将社会网络图分割为K个包含相同数目结点的子图,然后通过加入伪边和删除边的方法使得K个子图同构,增删边的数目和图数据可用性的大小主要取决于图分割策略.目标与邻居连接边上的属性值序列可以作为隐私攻击的背景知识.在文献中,通过加入伪点、伪边、设置边标签来弱化邻居连接边标签序列的标识作用.文献研究了如何阻止权重包导致的隐私泄露.

　　文献提出的加权图匿名化方法可以使得对于任意结点的权重包,至少有K.1个其他结点的权重包与其距离小于预先设定阈值,而不是完全相同;而文献提出的HA(histogramanonymization)算法使得至少有K.1个其他结点的权重包与其相同.显然,HA算法对于边及权重值的修改导致了图数据的统计特性的改变.例如,对于图查询Q:SELECTCOUNT(.edge.G)WHEREedge.weight≥2,在GHA中Q的查询结果是4,而Q在原图G中的查询结果是2,两者具有一定的偏差.为了提高匿名加权图的数据可用性,文献提出边权重概括技术(记作GA算法)来实现K-可能图.所谓K-可能图,是指对于任意结点的权重包,在K-可能图中可以找到至少K个为其概括实例的权重包.例如的GGA中,w12=[1,2]表示边e12的权重值位于区间[1,2],边e13上的50%表示e13的存在概率,因此,GGA中权重包w1可以表示为[([1,2],100%),(1,50%),(1,100%)].在图GGA中,结点1可被推测为中G的A,因为A的权重包wA是w1的一个可能实例;相似的,wA也是w4的一个可能实例;因此,A被准确识别的概率小于等于1/2.在GGA中执行查询Q时,边e23符合Q的查询条件,边e12和e34可能符合Q的查询条件,其他边不符合Q的查询条件,则Q的查询结果为区间[1,3],包含了Q在原图G上的查询结果2.实验结果证明,GA算法很好地保持了加权图数据可用性.

　　3.1.3数据扰乱

　　图数据扰乱隐私保护方法的基本思想是:通过对社会网络图进行随机化修改,使得攻击者不能准确推测出原始真实数据,从而起到保护社会网络数据隐私的作用。本文分别从数值扰乱和图结构扰乱等方面介绍基于数据扰乱思想的社会网络隐私保护技术.

　　（1）数值扰乱

　　社会网络中可以记录大量的数值信息,通过对数值信息进行随机化的扰乱和修改,可以使得攻击者不能猜测出原始真实数值.目前,数值扰乱[20,36]方法主要用于为加权图中的边权重提供隐私保护.

　　文献研究了通过扰乱技术保护社会网络边权重隐私的同时,降低扰乱噪声对于社会网络中两点间的最短路径序列及最短路径大小的影响.对于动态社会网络,文献提出在边权重中加入高斯噪声进行扰乱:*wi.wi(1.xi)(3)其中,i和*wi分别表示边i的初始权重、扰乱后权重;xi表示加入的高斯噪声,xi服从高斯分布N(0,.2).例如,采用服从N(0,0.152)分布的高斯噪声扰乱边权重后的社会网络.在静态社会网络中,为了保持指定结点对的最短路径序列及其大小不变,文献通过将社会网络数据中的边分类从而提出贪心扰乱算法,侧重扰乱其他边的权重.文献中的扰乱方法可以高效率地在边权重中加入噪声,并保证指定结点对的最短路径及其大小不变,但是噪声对于边权重的影响不大,仍然会泄露边权重隐私,而且不能保证所有结点间的最短路径保持不变,数据可用性不高.文献提出线性规划模型构建方法,在对边权重进行扰乱的同时,保持加权图的线性图性质,例如最短路径、K-最近邻等.与文献中仅能保持指定结点对的最短路径相比,文献中的方法较大程度地保证了加权图的数据可用性.

　　（2）图结构扰乱

　　通过随机进行图数据扰乱和修改,可以阻止攻击者获知原始图结构,从而保护社会网络数据隐私.图扰乱的主要方法是随机添加、删除边和交换边端点等.例如,参照图,很多图性质均与图谱相关,例如平均最短路径、社团结构、传递性等.为了保持图性质和图数据可用性,文献研究了如何进行图扰乱的同时保持图谱基本不变.文献指出,图谱主要由两个参数所决定:(1)图邻接矩阵最大特征值.1;(2)图拉普拉斯矩阵次最小特征值.2.通过研究图修改操作对于.1和.2的影响,文献提出的随机图扰乱技术总是选择保持.1和.2基本不变的图修改操作执行,从而保持图谱不变.虽然扰乱图在一定程度上保护了图数据隐私,但是存在明显缺陷:(1)与K-匿名图提供量化隐私保护不同(隐私泄露概率不大于1/K),图随机扰乱方法无法保证量化隐私保护,扰乱图中仍然存在隐私泄露威胁;(2)采用文献提出的图扰乱方法的必要条件是社会网络图是连通的,然而实际社会网络图一般不具有连通性,因此需要加入新边将图中的独立部分连接起来,使其具有连通性,引入了图噪声;(3)图特征值的计算代价很高,然而一次随机边修改操作需要多次图特征值的计算,导致边修改操作计算代价高,图扰乱需要大量的边修改操作,因此,文献的图扰乱算法的实际应用性不高.

　　3.1.4推演控制

　　所谓推演控制,是指对于不同隐私预测和推演模型,针对性地修改社会网络,使得攻击者采用预测模型不能推演出隐私信息,起到保护社会网络隐私的目的.在第2.4节中分别给出了基于邻居的预测模型和基于兴趣组的预测模型,然而,只有文献给出相应的推演控制技术来防止隐私泄露,因此,社会网络推演控制技术需要引起更多的关注.

　　在文献中,首先提出了基于共同邻居数目的敏感关系预测模型,并定义了两种链接推演攻击:单步链接推演攻击和级联链接推演攻击.单步链接推演是指对于图上的所有无边连接的结点对执行链接推演操作;级联链接推演,是指在图上执行多次单步链接推演操作.其次,为了阻止链接推演攻击,提出了一种基于链接世系溯源的防推演机制来切断敏感链接的推演路径,在保护社会网络中敏感关系的同时,保持了图数据可用性.推演控制技术能够有效地防止特定预测模型导致的隐私泄露,由于其针对性地修改社会网络,可以保持图数据的高可用性.但是推演控制技术的隐私保护能力有限,对于图数据隐私保护不具有通用性.

　　3.2动态性

　　当社会网络静止不变时,称该社会网络是静态社会网络;当社会网络是不断发展和变化时,该社会网络是动态社会网络,具有动态性.社会网络的动态性具体表现在:(1)不断有新结点加入社会网络中,原有结点从社会网络中退出,即结点的添加和删除;(2)社会网络中,两个无关系的实体建立新的边连接,网络中的某条边会被两个端点(实体)删除,即边的添加和删除.当前,社会网络隐私保护技术主要面向静态社会网络,而在现实中,几乎所有的社会网络都是动态的、不是静止不变的.从表3中可以看出,仅有少数隐私保护技术考虑了社会网络的动态性.

　　在文献中,除了给出面向社会网络的子图K-匿名技术,还研究了如何防止社会网络动态性和多次发布可能导致的隐私泄露.文献提出采用随机结点ID编码来保证动态发布匿名社会网络的安全性,其基本思想是:每次发布匿名社会网络时,同一结点被赋予不同的ID,从而阻止了攻击者基于网络变化信息获得数据隐私.显然,结点ID的重新编码不利于观察和分析网络的变化趋势,降低了动态网络的数据可用性.

　　与文献中研究如何防止网络动态性导致隐私泄露不同,文献研究了如何利用网络动态性来提高图匿名算法的执行效率.对于动态社会网络,当发布最新版本图数据时,基本做法是在当前图数据上重新运行图匿名化算法,当数据发布比较频繁时,则导致较低的执行效率.为了提高动态社会网络匿名算法的执行效率,文献提出采用动态网络预测技术来预测网络的变化趋势,例如某些无边连接的结点对在未来可能会增加边连接等,用于指导当前图数据的匿名化过程,目的在于减少未来图匿名化的重新计算量和负担,从而提高了动态发布过程中图匿名化的执行效率.

　　3.3并行性

　　随着网络技术的发展,社会网络数据的数量和规模都在不断地增长,呈现海量化趋势.对于海量社会网络数据,采用并行算法进行分析和处理,是提高效率的有效途径.目前,仅文献研究了云环境中社会网络隐私保护,而其他研究工作主要面向单工作站的社会网络隐私保护技术,不适用于海量社会网络数据.

　　在文献中,研究了在云环境中进行最短路径查询的同时保护图数据隐私,其研究目标是:攻击者不能推演出加权图中每个结点的邻居,数据查询者可以得到任意两点间的近似最短路径.文献中提出的云环境中隐私保护最短路径查询技术的基本思想是:将加权图G转换为链接图Gl和外包图集Go,其中,Gl相当于加权图的索引;而Go中的每个外包图符合“1-邻居-d-半径”安全要求,即攻击者无法获知任意结点的邻居以及距离小于d的结点对,对于输入的最短路径查询,基于Gl找到相应的外包图进行最短路径的求解;每个外包图存储在云环境的节点中,记录了符合安全条件的结点对之间的最短路径距离,通过采用三角不等式来逐步求精最短路径查询结果.由于在构建链接图Gl和外包图集Go时需要计算大量结点对之间的最短路径,使得大型加权图的分割和预计算的工作量很大,当网络动态变化时,链接图Gl和外包图集Go均需要重新计算,而文献没有考虑如何动态更新链接图Gl和外包图集Go.

　　4、数据可用性与实验评测

　　社会网络图匿名化会导致一定的信息损失,影响图数据可用性.不同社会网络隐私保护技术对图数据可用生不同的影响,需要通过实验测试来分析和评估匿名化对数据的影响.本节归纳了常用的社会网络隐私保护技术的实验评测指标,其中包括结点数据可用性、边数据可用性、图结构及性质、图查询、执行效率等方面.

　　在社会网络中,结点可能会具有表示类别的标签、与实体相关的属性值等信息,边可能会具有标签、权重等信息,而图匿名技术通常会对这些属性值进行修改、概括(generalization)等匿名化操作,因此需要评估图匿名化导致的结点和边的属性值信息的损失.如第3节中,添加和删除边是图匿名化中最基本的图修改操作,可以将图匿名化过程中的边增加和删除数目作为一种图信息损失的度量.特殊地,文献通过加入结点来获得K-对称图,因此不仅评测了边的添加数目,同时也测试了不同隐私要求下加入结点的数目.

　　在图结构及性质的实验测评中,结点度分布、最短路径、传递性是比较常见的图数据可用性度量标准.结点度分布是图中不同结点度的频率统计,是描述图状态的一种基本图性质.最短路径分布统计了图中两点间最短距离的分布,由于社会网络中结点数目巨大并且最短路径计算代价大,因此在实验测试中计算最短路径分布时,通常随机选取指定数目的结点对来进行计算.

　　所谓传递性(又称聚集系数),是指一个结点所有邻居对中具有边连接的比例,即描述了“一个人的两个朋友也是朋友的概率”.当按照度由大自小删除图中结点时,网络适应力表示图中最大社区所包含的结点数目,网络适应力描述了由于网络攻击导致部分结点通信不畅时网络的连通性.所谓传染性,是指对于一种假想疾病,当随机选择某个结点作为传染源时,在指定传染率下被传染结点的比例.为了测量社会网络图中社区结构变化大小,在文献中定义了层次社区熵(hierarchicalcommunityentropy)来计算图匿名化所导致的社区结构的变化.