基于信息损失量估计的匿名图构造方法  

Method of constructing an anonymous graph based on information loss estimation

作　　者：苏洁[1] 刘帅[1] 罗智勇[1] 孙广路[1] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,黑龙江哈尔滨150080

出　　处：《通信学报》2016年第6期56-64,共9页Journal on Communications

基　　金：黑龙江省自然科学基金资助项目(No.A201301);黑龙江省教育科学规划课题基金资助项目(No.GBC1211062);黑龙江省普通高等学校新世纪优秀人才培养计划基金资助项目(No.1155-ncet-008);黑龙江省博士后基金资助项目(No.LBH-Z12082)~~

摘　　要：首先分析了在进化的社会网络序列中,攻击者利用节点度信息,通过识别目标节点的方法对局部社会网络进行攻击过程,分析了利用k匿名方法对该类攻击进行隐私保护时存在的信息损失问题,针对该问题,提出了一种基于信息损失量估计的k匿名图流构造方法,通过子图节点属性泛化、子图内部结构的泛化控制图重构的信息损失,通过禁止子图内部扰动阻止网络攻击。定义匿名过程中由于图重构造成的节点和结构信息损失的估算方法,建立了基于贪婪聚类算法的网络节点的k匿名聚类算法,根据信息损失估计实现匿名分组,在进化的社会网络中以最小信息损失量构造匿名社会网络,在医疗诊断数据集上的实验表明所提方法能够较理想地控制信息损失量。A potential attack based on degree information by re-identifying target vertexes from a sequence of published graphs was analyzed. To deal with this kind of attack, a k-anonymous graph stream constructing method based on information loss estimation was provided. Information loss caused by re-constructing graph was controlled by using the method of attributes generalization of nodes and the structure generalization of sub-graph. The disturbance in sub-graph was forbidden to prevent the attack. The method of measuring the information loss of nodes and structures during the anonymous process due to re-construction of graph was defined. A k-anonymity cluster algorithm based on greedy clustering algorithm was build, which realized anonymous partition according to the information loss. Finally, a method of constructing anonymous social network for the evolving social network with the least information loss was provided. The experiments on medical diagnostic data set show that the algorithm of constructing anonymous graph based on the information loss estimation can be used to control the loss of information.

关 键 词：社会网络 隐私保护 k匿名 信息损失估计 

分 类 号：TP309.2[自动化与计算机技术—计算机系统结构]