邻居子图扰动下的k-度匿名隐私保护模型.pdf

收稿日期:网络出版时间:基金项目:国家自然科学基金();贵州财经大学校级在校生科研项目(Z X S Y )作者简介:丁红发(),男,副教授,E m a i l:h o n g f a d i n g f o x m a i l c o m唐明丽(),男,贵州财经大学硕士研究生,E m a i l:q q c o m刘海(),男,副教授,E m a i l:q q c o m蒋合领(),男,讲师,E m a i l:q q c o m傅培旺(),男,贵州财经大学硕士研究生,E m a i l:q q c o m于莹莹(),女,贵州财经大学硕士研究生,E m a i l:q q c o m网络出版地址:h t t p s:/k n s c n k i n e t/k c m s/d e t a i l/T N h t m ld o i 敭 j 敭i s s n 敭 敭 敭 邻居子图扰动下的k度匿名隐私保护模型丁 红 发,唐 明 丽,刘海,蒋 合 领,傅 培 旺,于 莹 莹(贵州财经大学 信息学院 贵州省大数据统计分析重点实验室,贵州 贵阳 ;贵安新区科创产业发展有限公司,贵州 贵阳 )摘要:大规模图数据在商业和学术研究中应用广泛,在其共享发布场景中隐私保护极为重要.现有的匿名隐私保护模型难以有效解决图数据隐私保护和数据效用间的冲突问题.针对此问题,基于邻居子图扰动提出一种增强隐私保护程度和数据效用水平的k度匿名隐私保护模型.首先,该模型利用邻居子图扰动机制优化扰动图数据节点的 邻居子图,提高扰动效率并减少数据效用损失;其次,利用分治策略并依据节点度序列实现对节点匿名组的优化划分,提高匿名图数据的效用;最后,采用边修改和子图边缘修改的策略重构匿名图数据,实现图数据k度匿名隐私保护.对比和实验结果表明,所提出模型比现有模型在计算开销和安全性方面有了较大提升,能够同时抗节点度攻击和邻居子图攻击,在边变化比例、信息损失、平均节点度变化和聚类系数等指标方面数据效用显著提升.关键词:隐私保护技术;图结构;匿名;k度匿名;邻居子图中图分类号:T N ;T P 文献标识码:A文章编号:()M o d e l f o rp r o t e c t i o no fk d e g r e ea n o n y m i t yp r i v a c yu n d e rn e i g h b o r s u b g r a p hd i s t u r b a n c eD I NGH o n g f a T ANG M i n g l i L I U H a i J I ANG H e l i n g F UP e i w a n g Y UY i n g y i n g 敭 G u i z h o uK e yL a b o r a t o r yo fB i gD a t aS t a t i s t i c a lA n a l y s i s C o l l e g eo f I n f o r m a t i o n G u i z h o uU n i v e r s i t yo fF i n a n c ea n dE c o n o m i c s G u i y a n g C h i n a 敭 G u i a nS c i e n c ea n dT e c h n o l o g yI n d u s t r yD e v e l o p m e n tC o 敭 L t d 敭 G u i y a n g C h i n a A b s t r a c t W i t ht h e i n c r e a s i n gu s eo fm a s sg r a p hd a t a i nc o mm e r c ea n da c a d e m i a i th a sb e c o m ec r i t i c a l t oe n s u r ep r i v a c yw h e ns h a r i n ga n dp u b l i s h i n gg r a p hd a t a 敭 H o w e v e r e x i s t i n ga n o n y m o u sp r i v a c y p r e s e r v i n gm o d e l ss t r u g g l e t ob a l a n c et h ec o n f l i c tb e t w e e np r i v a c ya n du t i l i t yo fg r a p hd a t a 敭 T oa d d r e s st h i si s s u e ak d e g r e ea n o n y m i t yp r i v a c yp r e s e r v i n gm o d e lb a s e do nn e i g h b o rs u b g r a p hp e r t u r b a t i o nh a sb e e np r o p o s e d w h i c he n h a n c e sb o t ht h el e v e l so fp r i v a c yp r e s e r v a t i o na n dd a t au t i l i t y 敭 T oa c h i e v ek d e g r e ea n o n y m i t yp r i v a c yp r e s e r v a t i o n t h i sm o d e l f i r s tp e r t u r b s t h e n e i g h b o r s u b g r a p ho fe a c hn o d e i ng r a p hd a t ab yu s i n gn e i g h b o r s u b g r a p hp e r t u r b a t i o n 敭 T h i sp e r t u r b a t i o ni so p t i m i z e d r e s u l t i n gi ni m p r o v e dp e r t u r b i n ge f f i c i e n c ya n dr e d u c e dd a t au t i l i t y l o s s 敭 N e x t t h ep a r t i t i o no f a n o n y m o u sn o d eg r o u p i so p t i m i z e db yu s i n gad i v i d e a n d c o n q u e r s t r a t e g yb a s e do nt h ed e g r e es e q u e n c eo fn o d e s l e a d i n gt oi m p r o v e du t i l i t yo ft h ea n o n y m i z e d 年月第 卷第期西安电子科技大学学报J OURNA LO FX I D I ANUN I V ER S I TYA u g V o l N o h t t p:/j o u r n a l x i d i a n e d u c n/x d x bg r a p h 敭 F i n a l l y t h ea n o n y m i z e dg r a p h i s r e c o n s t r u c t e db ye d i t i n gb o t he d g e sa n ds u b g r a p hb o r d e r s t oa c h i e v ek d e g r e e a n o n y m i t yp r i v a c yp r e s e r v a t i o n 敭 C o m p a r i s o n s a n de x p e r i m e n t sh a v e s h o w n t h a t t h ep r o p o s e dm o d e lg r e a t l y i m p r o v e sb o t ht h eo v e r h e a da n ds e c u r i t yw h e nc o m p a r e dt oe x i s t i n gm o d e l sa n dt h a t i ti sa b l et or e s i s t b o t hd e g r e e b a s e da t t a c k s a n dn e i g h b o r h o o da t t a c k s 敭 F u r t h e r m o r e t h ed a t au t i l i t y i sg r e a t l y i m p r o v e d a se v i d e n c e db ym e t r i c s s u c ha s c h a n g ep r o p o r t i o no f e d g e s i n f o r m a t i o n l o s s c h a n g e i n t h e a v e r a g ed e g r e eo fn o d e s a n dc l u s t e r i n gc o e f f i c i e n t 敭K e yW o r d s p r i v a c y p r e s e r v i n g t e c h n i q u e s g r a p h s t r u c t u r e s a n o n y m i z a t i o n k d e g r e e a n o n y m o u s n e i g h b o r s u b g r a p h 引言互联网、移动物联网的高速发展产生了社交网络、移动轨迹、引文网络、邮件网络等海量图结构数据,且被广泛应用于学术研究、数据挖掘、广告、商业决策支持、疾病传播研究等领域.此类图数据在创造巨大社会价值和经济价值的同时,还涉及大量个人隐私(如身份信息、政治倾向、个人喜好、地理位置等敏感信息),在共享、分析及应用图数据过程中极易造成隐私泄露,引发了人们对隐私和安全的担忧.例如,年,美国社交媒体脸书(F a c e b o o k)超亿用户的个人数据泄露,其中包括电话号码、电子邮件等;年月,滴滴因个人轨迹信息、地图信息等数据安全问题被罚 亿人民币,再次警示从事数据搜集、存储、传输及使用的企业,应当增强数据隐私保护能力,直面图数据存储、使用中存在的安全问题,防范信息泄露风险.上述事件均表明社交网络、个人轨迹等图数据安全与隐私问题已成为当前社会一个亟待解决的重要问题.因此,研究图结构数据的隐私保护模型与算法变得尤为重要.大规模图数据共享发布过程中,图数据节点属性和关系属性两类重要隐私信息易受到度信息攻击、子图攻击及链接攻击等结构化攻击.简单的匿名方法(例如,删除图数据节点的标识符)已经被认为是一种低效的匿名化机制,其无法可靠地保护节点的隐私.因此,隐私保护效果更好的各类匿名化隐私保护模型被相继提出 ,以防止图数据的隐私信息泄露,并防御针对图数据隐私的恶意分析和提取攻击.匿名化隐私保护模型通过将具有相同结构性质的节点数扩充至少k个,从而使得攻击者对图数据隐私节点的攻击命中率降低至/k以下,并且匿名化模型可分别从节点的度、子图及节点标签等属性出发,对图数据进行隐私保护 .另一种比较流行的图数据隐私保护方法是差分隐私 ,其在实现过程中具有严格的数学理论证明.然而,差分隐私通常适用于发布图数据的统计信息,无法实现精确的子图模式匹配以及生成完整图数据.此外,差分隐私的隐私保护效果往往依赖于经验选择一个较优的隐私预算,在实际应用中效果通常难以控制.相比于差分隐私,匿名化由于算法简单、计算开销低、隐私保护效果易控制等特性,已被广泛用于各类商业应用中的图数据隐私保护.因此,研究匿名化图数据隐私保护方法具有重要的理论和实践意义.目前,实现图数据匿名隐私保护的途径主要有两种:基于聚类的匿名化方法 和基于图修改的匿名化方法.基于聚类的方法 是通过对图的节点、边或对两者同时聚类,从而形成不可区分的匿名组.图数据同一匿名组中的节点泛化后可聚类构成超节点,同一匿名组中的边可聚类构成超边,通过超点和超边构成超图从而保护待共享发布图数据的隐私.YA Z D AN J U E等 提出了一种基于节点连接结构和属性值的属性图聚类匿名化方法,综合节点间的结构和属性相似度,将社交网络图数据所有节点聚类成一些包含节点个数不小于k的超点;L ANGA R I等 提出了一种基于k成员模糊聚类和萤火虫算法的组合匿名算法,使用模糊c均值来构建至少有k个成员的平衡聚类簇以保护匿名社交网络图数据不泄漏身份、属性和链接隐私,并能抵抗相似性攻击;HONG等 通过采用多维排序方案和基于贪婪分区的聚合技术设计了有向社交网络数据的k度匿名模型.综上所述,基于聚类的匿名方法通过聚类隐藏了超节点里面节点间的关系,能保护图数据中的隐私信息,但该方法将使超节点内部的数据效用急剧下降,因此仅适用于不需要公开数据内部结构的大规模图数据的场景.基于图修改的方法是通过修改图数据中的部分节点和边,实现对图数据中隐私信息进行保护的匿名化技术.L I U等 提出了一种运用贪心策略增加边和噪声节点的方式来实现图结构数据的k度匿名算法,使第期丁红发等:邻居子图扰动下的k度匿名隐私保护模型h t t p:/j o u r n a l x i d i a n e d u c n/x d x b得任何节点均至少与其余k个节点度数相同,该方法在能够抵御节点度攻击的同时严重改变了图数据的关系结构和连通性;随后,L I U等 设计了一种基于新的度序列划分算法的社交网络数据发布隐私保护算法,该方法仅通过增边和添加节点实现了k度匿名,但其信息损失过大;B A Z GAN等 证明了利用不改变顶点/边数的边旋转实现图的k度匿名问题是非确定多项式(N o n d e t e rm i n i s t i cP d y n o m i d o,N P)困难的;Z HOU等 提出了一种比k度匿名保护效果更强的隐私保护模型k邻居匿名,除了对节点度数实现了k匿名,还对节点的邻居结构实现了k匿名,但该方法不能抵抗子图攻击;CHE NG等 提出了一种通过实现子图间同构的图数据k同构匿名方法,可抵御子图匹配攻击;此外,Z OU等 提出了基于图自身同构的图数据k同构匿名方法,也能抵御子图匹配攻击.k同构和k自同构方式实现了更强的隐私保护效果 ,但因其破坏图数据的关系结构会造成巨大的信息损失,显著降低了匿名后的数据效用.为了提高数据效用,L I ANG等 将k匿名性定义为数学优化问题,试图实现图数据k匿名的同时最大化数据效用;S HAK E E L等 使用一种贪婪算法,在原始图中插入最少数量的虚拟连接来实现防止共同朋友攻击的k度匿名方法.综上所述,基于图修改的匿名方法使用增、删节点和同构的方式实现k匿名,一定程度上增强了隐私保护效果,但存在信息损失较大和图结构特性改变较大的问题.为解决现有图数据匿名隐私保护方法存在的隐私保护强度不足和信息损失较大的问题,文中提出一种基于邻居子图扰动 的k度匿 名隐私保 护模型(k D e g r e ea n o n y m i t yp r i v a c yp r o t e c t i o n m o d e lb a s e do nN e i g h b o r h o o ds u b g r a p hD i s t u r b a n c e,N D K D).该模型利用最小化边扰动机制实现每个节点的 邻居子图扰动,提高该模型的抗隐私攻击能力;采用分治法优化匿名组划分,以减少对图数据结构的改变从而提高数据效用;此外,该模型引入两种新的图匿名修改方法:边缘添加和边缘删除,实现不增删节点而生成k度匿名图.通过上述措施,该模型能有效抵御 邻居子图和节点度背景知识攻击,仍然具有较好的数据效用和图数据结构特性.具体而言,主要贡献有:()提出了一种邻居扰动后的k度匿名模型,通过改进邻居匿名和度匿名算法,实现对 邻居子图和节点度的背景知识攻击的抵御.()改进了k度匿名算法,采用分治法优化匿名组的划分,减少匿名过程中节点的信息损失.引入了新的图匿名化操作方式:边缘添加和边缘删除,在保持原始图的节点数量条件下将图数据重构成完全满足k度匿名的匿名图.()在S t a n f o r dN e t w o r kA n a l y s i sP r o j e c t(S NA P)真实数据集上对所提方案及相关k匿名方案进行实验对比.结果表明,相较于传统k匿名方案,文中所提匿名模型具有更优的数据效用,且图结构特性改变更小.相关定义文中将图数据建模为无向、无标签、无加权的简单图G(V,E),V表示图G中所有节点的集合,E表示图G中节点之间的关系集合,即边的集合,且EVV.本节介绍图数据发布匿名化隐私保护相关的概念和定义.k度匿名定义(图的k度匿名模型)给定图G(V,E),viV,在V中至少存在k个不同于vi且与节点vi拥有相同度数的节点,则图G满足k度匿名.k度匿名的图G,满足图中任意节点与拥有相同度的其它节点,在度上不可区分,故节点的度攻击对于k度匿名图的命中率小于等于/k.定义(递减度序列)若图G(V,E)中的节点集V(v,v,vn)中所有节点按照递减度的偏序关系排列,即ds e qd(vi)d(vi)|viV,in,则该节点的度序列是递减度序列.定义(节点集gj的信息损失)所有属于节点集gj的节点,匿名前后节点的度值变化的和,即I(gj)n id(vi)d(v i),为节点集gj的信息损失.其中,gj为节点集V的子集,n 表示节点集合gj的节点个数,西安电子科技大学学报第 卷h t t p:/j o u r n a l x i d i a n e d u c n/x d x bvigj,d(vi)表示节点vi的度,v i表示节点vi匿名后的节点.信息损失越小,匿名图数据的信息丢失量就越低.k邻居匿名定义(邻居子图)图G中节点v的邻居子图,定义为G中包括v在内的所有与v直接相连的节点,以及这些节点之间的所有边构成的子图,如图所示.图(b)为节点v在图(a)的邻居子图.(a)图G(b)图G上节点v的邻居子图图邻居子图定义(k邻居匿名)若图G的任意一个节点viV,在节点集V中至少存在k个不同于vi且与vi拥有相同邻居子图的节点,则图G满足k邻居匿名.定义(边的邻接点)给定图G(V,E),viV,vjV.若V中存在节点v,使得ev,viE,ev,vjE,则v称为边evi,vj的邻接点.N D K D隐私保护模型和算法设计针对图结构数据发布场景的隐私保护,文中提出了一种基于邻居扰动的k度匿名的隐私保护模型N D K D.为便于理解,首先在节 描述所提N D K D隐私保护模型的具体框架,其次在节 阐述该模型框架中各步骤的算法原理.N D K D隐私保护模型框架所提N D K D隐私保护模型由邻居扰动、度序列匿名和重构图个模块构成,具体框架如图所示.在图中,N D K D隐私保护模型的个模块即匿名化隐私保护的个核心环节,按照邻居扰动、度序列匿名和重构图的顺序对原始图数据进行处理.图N D K D匿名化隐私保护模型框架N D K D模型的基本思想是:对原始图数据中的节点进行邻居扰动,使得扰动后的图数据不能被基于 邻居子图的背景知识准确识别.同时,邻居扰动保留了原始图数据中大量节点的度值,即图数据中的绝大多数节点的度值未发生变化,但是这也使邻居扰动后的图数据依然无法抵御节点度攻击.基于此问题,对邻居扰动的图数据进行基于最大邻居差划分的k度匿名,结合匿名参数k,对邻居扰动后的图数据节点的递减度序列进行处理,生成节点集的匿名组.按照匿名组中节点度对邻居扰动后的图数据进行图修改操作,第期丁红发等:邻居子图扰动下的k度匿名隐私保护模型h t t p:/j o u r n a l x i d i a n e d u c n/x d x b重构成k度匿名的图数据,使得重构后的图数据不能被基于节点度的背景知识准确识别.将匿名后的图数据进行共享发布.该模型的个模块又分为若干个具体的步骤.邻居扰动模块首先将原始图数据的节点集映射到节点的递减度序列,遍历递减度序列中的节点,并找到与遍历的节点有最多邻居节点的另一节点;然后,改变两个节点之间边的状态.重复上述操作,直至原始图数据中每个节点的 邻居子图都进行了扰动.度序列匿名模块首先根据参数k的值,采用分治思想,找到每个度序列之间的最大邻居差,用最大邻居差值将节点度序列划分为长度更小的度序列,直到所有的度序列的长度介于k至k之间;其次,根据度序列匿名的信息损失,在最小信息损失的约束下,为每个度序列设置目标度,实现节点度序列的匿名化.重构图模块在增、删和移边操作的基础上,进行边缘添加和边缘删除操作,重构成匿名化的图数据.为了进一步提高对图所示的N D K D匿名化隐私保护模型框架的理解,图以一个具体的简单图为例,结合所提出的隐私保护模型框架,阐述实现匿名参数k为时的匿名化隐私保护过程.(a)原始图数据(b)邻居扰动(c)图重构(d)匿名图数据图基于N D K D模型的度匿名化过程示例第步,对原始图数据进行邻居扰动.首先,将原始图数据(如图(a)节点的度按照递减排序,递减度序列为ds e q,.其次,对所有节点按照递减度序列的顺序进行邻居扰动.最大度节点 的边e,拥有个邻居节点,因此删除边e,.此时,邻居子图发生扰动的节点有个,即节点、节点、节点、节点和节点.排除这个节点,继续对剩下的节点进行扰动.扰动后,最终得到图(b),其中虚线代表删除边,粗线代表增加边.由于度为的节点仅能通过节点度进行匹配,因此邻居扰动过程不对度为的节点做处理.第步,对节点度序列进行匿名化.首先,采用分治法对图(b)的递减度序列ds e q,进行划分.具体而言,在递减度序列的第个数和倒数第个数之间找到最大邻居差值,并在最大邻居差为处对递减度序列进行划分,得到两个度序列,.对序列长度大于的序列继续进行上述操作,直至所有度序列均符合长度大于等于k且小于等于k的条件,最后划分的度序列为,.其次,分别计算各划分后的度序列的目标度,并赋值给各度序列,得到匿名组,.第步,根据匿名组对扰动后的图进行图重构.根据前一步所得到的匿名组度数,对第步所得到的扰西安电子科技大学学报第 卷h t t p:/j o u r n a l x i d i a n e d u c n/x d x b动图进行重构.具体而言,对图(b)中两个度数为的节点和 减少其度数.如图(c)所示,这两个度为的节点之间存在边,采用删边操作删除边e,得到符合匿名组度数要求的图,如图(d)所示.经过上述基于邻居子图扰动的度匿名化过程,图(a)中任意节点的 邻居子图都无法在图(d)中进行匹配;匿名后的图数据(如图(d)中的任意节点度都至少与其它个节点度数相同,节点度的攻击命中率降低到/以下.N D K D隐私保护模型的算法设计基于图中匿名隐私保护模型的个模块,设计实现核心功能的具体算法.节 提出邻居扰动模块中的节点 邻居子图扰动算法,该算法确保每次扰动的边所涉及的 邻居子图包含尽可能多的节点,从而在满足原始图数据节点 邻居子图扰动的前提下使得图中扰动边的数量最少.节 首先提出度序列匿名模块中最大邻居差划分度序列步骤的算法和计算度序列的目标度步骤的计算公式,最大邻居差划分度序列算法通过分治法查找度序列的最大邻居差来划分度序列,避免同一度序列出现节点度的差值较大的情况.其次,对匿名组度数之和不为偶数时的操作进行了说明.节 提出重构图模块中的图数据边修改算法,利用增、删和移边以及边缘添加、边缘删除生成匿名图数据.节点 邻居子图扰动的算法在对图数据进行k度匿名之前,若存在图数据或图中大部分节点原本就满足k度匿名的情况,则k度匿名后的图数据的大部分节点会保留原始图数据中的结构信息.根据定义,k度匿名后的图数据可以使攻击者不能根据节点的度信息对某个节点进行唯一识别,但是攻击者若掌握了某节点的 邻居子图信息,则依然可以根据节点的 邻居子图唯一识别该节点.因此,文中在k度匿名之前,对图数据进行 邻居子图的扰动,使得任意情况的图数据在匿名之后,均无法被攻击者所掌握的 邻居子图信息唯一识别.由定义和定义可知,若某条边e在节点v的邻居子图中,那么节点v一定在边e的邻接点中.图中的任意一条边evi,vj的修改,都会改变evi,vj的邻接点的 邻居子图.基于图数据的该特性,本节提出最少边的数量改动的 邻居子图的扰动方式.通过对每次计算得到的拥有最多邻接点的边进行扰动,保证在图数据中任意节点的 邻居子图至少有条边进行了扰动的前提下,扰动的边数最少.具体如算法所示.算法节点 邻居子图扰动的算法.输入:原始图数据G输出:邻居扰动后的图数据G f o rvii nds e q:/ds e q为图G的节点集的递减度序列 vjS e a r c h_M a x_NN e i g h b o r(vi)/vj为与节点vi有最多邻居节点的节点,且ij i fevi,vjG d e l e t eevi,vj e l s e:a d devi,vj i fevi,vmGa n devj,vmG:/vm为满足条件的所有节点 d e l e t eNN e i g h b o rvi,NN e i g h b o rvj,NN e i g h b o rvm/NN e i g h b o r为G未修改 邻接子图节点的邻接矩阵r e t u r nG 算法按图G的递减度序列进行遍历,对所有节点的 邻居子图的至少条边进行修改,直至所有V中所有节点的 邻居子图都进行了修改.由于度为的节点不具有 邻居子图,因此此步骤中不考虑度为的节点.在扰动完成后的图中,原始图数据中任意节点的 邻居子图都无法进行匹配.算法在进行邻居扰动过程中会使部分节点的度值发生变化,造成图数据的部分信息损失,但是该算法保证了进行扰动的边尽可能地少,所以对算法的匿名过程中数据效用损失的影响非常小.对图数据进行 邻居子图扰动的过程中,若每次计算全图中边邻接点数量,则会造成O(n)的时间开销比较大.考虑到边evi,vj的邻接点数量等于边两端节点vi和vj的共同邻接点数量,也就是说,若某条第期丁红发等:邻居子图扰动下的k度匿名隐私保护模型h t t p:/j o u r n a l x i d i a n e d u c n/x d x b边evi,vj的邻接点数量较多,则该边两端节点vi和vj的共同邻接点数量较多,而节点vi和vj的度数一定大于它们的共同邻接点数量,所以,边的端节点度数大是该边拥有较多邻接点的必要条件.从另一方面来看,较小度节点所在边的邻接点数量一定小于该节点的度,若从度数最小的节点开始遍历,则每次扰动边的的邻接点数量较少,就会使得图数据 邻居子图扰动过程中扰动边的数量过多,从而造成较大的数据效用损失.为了降低计算开销,对于拥有最多邻接点的边的遍历可以替换为最大度数节点的遍历.综上,在算法中采用一种贪婪的算法,每次只对未扰动最大度的节点所在的边进行计算.步骤对节点的递减度序列进行遍历,遍历的每个节点都是当前未扰动的最大度值的节点.步骤是查找遍历的节点vi拥有最多邻接点的邻边.步骤,使得每次扰动的边,包含了尽可能多的节点,从而降低扰动边的数量.步骤,对vi、vj之间的边的状态进行扰动.步骤,引入了图G的邻接矩阵NN e i g h b o r,该邻接矩阵记录未扰动 邻居子图的节点,并将发生扰动的节点从该矩阵删除,避免对同一个节点的 邻居子图重复扰动.重复上述操作,直至NN e i g h b o r为空.最后返回邻居扰动后的图G.在算法中,NN e i g h b o r的大小从m跳跃式地递减,递减速度受图数据结构的影响,其中m为图G(V,E)中边的数量.若NN e i g h b o r从m跳跃式地递减到需要a次,则遍历次数为a,所以遍历次数取决于NN e i g h b o r的递减速度.因此算法的时间复杂度最好的情况为O(m),最坏的情况为O(m),平均情况为O(m).算法的空间复杂度为O(m).最大邻居差划分度序列算法和计算度序列的目标度的方法)最大邻居差划分度序列算法在划分匿名组的过程中,度序列的两个邻居之间的差异会影响划分结果.例如,个度序列ds e q,包含个节点的度.邻居差是指节点度的差值.若匿名参数k为,则度数为与度数为的两个相邻节点的度差异最大为.在最小信息变化量和匿名参数k的约束下,最优的匿名划分为,和,.度序列最大邻居差的划分采用了分治的思想,同时为了避免采用递归方法造成空间复杂度开销过大的问题,算法采用非递归方法实现,在O(n)的时间复杂度内解决节点子序列的划分问题.对整个节点集合V 子序列的划分,等价于节点度递减序列的划分,将递减度序列邻居差异的划分问题,分解为几个匿名子序列划分的问题.对于每个长度大于k的匿名子序列,都可以划分为两个或两个以上的子序列.因此,每次查找最大邻居差需要在匿名序列的第k个元素和k个元素内寻找.具体如算法所示.算法最大邻居差划分度序列算法.输入:匿名参数k和图G 的递减度序列ds e q输出:匿名序列划分的最大邻居差下标N e i g_d i f fiM a x_N e i g_D i v i s i o n(ds e q,k)/k为匿名参数,i为ds e q最大邻居差节点的下标 N e i g_d i f f a p p e n d(,i,n)/将最大邻居差的节点的下标以及,n添加到N e i g_d i f f w h i l e f l a g T r u e:/f l a g记录下标之间是否还存在距离大于k的情况 f l a g F a l s e f o rp,qi nN e i g_d i f f:/p,q为已记录的最大邻居差下标的两个相邻下标 i f qpk:iM a x_N e i g_D i v i s i o n(p,q,k)N e i g_d i f f a p p e n d(i),f l a g T r u er e t u r nN e i g_d i f f算法中,首先将邻居扰动之后的图数据,按定义进行节点度序列的降序排序.然后根据匿名化参数k和最大邻居差,将图G 划分为满足k匿名的度序列.该算法的划分从全图的度序列开始,避免了将邻居差过大的节点划分到同一匿名组,从而造成信息损失过大的问题.其次,该算法采用了非递归的算法,避免了递归方法中空间复杂度开销过大的问题.算法中,步骤是查询图G的递减度序列的最大邻居差,并记录到N e i g_d i f f中.每次查找最大邻居差的时间复杂度为O(n),空间复杂度为O().步骤为采用循环的方式查找长度大于k的西安电子科技大学学报第 卷h t t p:/j o u r n a l x i d i a n e d u c n/x d x b序列的最大邻居差下标,直到采用所划分的度序列长度介于k,k,从而满足匿名序列的长度要求.其中,对N e i g_d i f f的遍历次数介于nk和nk之间,每次查找最大邻居差下标的时间复杂度为O(n),其中n为图G 的节点数量.节点度序列的空间复杂度为O(n),N e i g_d i f f的空间复杂度为O(n).因此该算法的时间复杂度为O(n),空间复杂度为O(n).)计算度序列的目标度的方法由于使用遍历搜索来选择匿名节点的目标度数对于大规模图数据时间复杂度的开销过大,因此文中使用一种贪婪的方法 来降低搜索的复杂性.该方法将度序列的节点平均值作为该序列的目标度,但是度序列的节点平均值可能不是整数,因此引入两个值mj,mj.其中,mj是节点集gj的度序列与属于该组的所有节点度的平均值的差值的总和,使用下取整函数将平均值四舍五入.mj以同样的方式计算,但使用了上取整函数.mj与mj的计算方法由式()、式()给出:mjvigj(d(vi)gj),()mjvigj(d(vi)gj),()其中,d(vi)表示节点的度数,gj表示匿名组gj中节点度数的平均值,代表向下取整数,代表向上取整数.第个方程使用gj度均值的下界,第个方程使用gj度均值的上界.然后,使用Pj,Pj分别来计算gj的目标度为gj下取整和上取整的概率.概率值越大,信息损失就越小,该值作为该节点集gj的目标度就越优.Pj,Pj的计算方法由公式()、式()给出:Pj(mj)mjmjmj,()Pj(mj)mjmjmj,()其中,Pj为匿名组gj使用均值下界作为目标度的概率,Pj为匿名组gj使用均值上界作为目标度的概率.为划分好的度序列赋值目标度后得到匿名组.匿名后所有节点目标度的和必须是偶数,因为每条边在度序列中被计数两次.在匿名度序列划分以及计算出各匿名组的目标度之后,如果出现图的节点目标度之和为奇数的情况,则对划分的匿名组进行回溯,找到拥有最小奇数差值的邻居差值的匿名组gi,gj.在两个匿名满足式()的条件下,更改匿名组gi的最后一个节点放入gj中,或者将gj第个节点放入gi中,实现最小信息损失的满足匿名图中节点度数必须为偶数的要求:M i n_D i f fm i n(d(vi)d(vj)|ij,vigi,vjgj,(d(vi)d(vj),(gik)gj(k)(gi(k)gjk),()其中,gj为匿名组gj的节点个数.重构图算法图G 的节点与其在匿名组中的关系有种:节点vi小于其在匿名组v i度数,即d(vi)d(v i);节点vi大于其在匿名组v i度数,即d(vi)d(v i);节点vi等于其在匿名组v i度数,即d(vi)d(v i).图中任意边的修改状态由边两端的节点状态共同决定.对于原图中边的两端节点度数同时大于或小于其在匿名序列中节点目标度的情况,采用删边和增边,使其边两端节点度接近或达到其在匿名序列中的目标度,如图(a)所示.而对于边的两端节点d(vi)d(v i),d(vj)d(v j)的情况,引入第个节点vp,先删除evj,vp之间的边,再添加evi,vp之间的边,也就是移边.在移边过程中第个节点vp的度数不变.如图(b)所示,其中虚线边代表删除的边,粗线代表增加的边.需要注意的是,在重构简单图过程中,单个节点不能单独增加边;已存在边的两个节点不能再增加边;不存在边的两个节点不能删除边.仅依靠增边、删边和移边种方式,并不能保证图G 能够完全重构成满足匿名序列节点的图.例如,当图重构过程中,可能出现仅剩的节点vi和vj之间不存在边evi,vj,同时d(vi)d(v i)且d(vj)d(v j)时,则无法用删边或移边策略.同理,在图重构的过程中仅剩的节点vi和vj第期丁红发等:邻居子图扰动下的k度匿名隐私保护模型h t t p:/j o u r n a l x i d i a n e d u c n/x d x b之间存在边evi,vj,同时d(vi)d(v i)且d(vj)d(v j)时,则无法采用增边或移边策略.(a)增边、删边(b)移边图增边、删边和移边匿名化操作方式为了解决上述问题,在重构图的过程中,引入另外两个不同于节点vi和vj的节点vp和vq,并采用边缘添加和边缘删除策略,如图所示.(a)边缘添加(b)边缘删除图边缘添加、边缘删除匿名化操作方式在采用边缘添加和边缘删除时,需要避免某个节点匿名前后的度变化过大.因此,创建一个序列C h a n g e_d记录每个节点匿名前后的度值变化的大小,并将序列按度值变化大小递减排序.算法重构图算法.输入:邻居扰乱后的图G(V,E)和匿名后度发生变化的节点集合C h a n g e_d输出:满足邻居子图扰动下的k度匿名的图G(V,E)f o rvi,vji nC h a n g e_d:i f