通信学报 ›› 2016, Vol. 37 ›› Issue (6): 56-64.doi: 10.11959/j.issn.1000-436x.2016116

• 学术论文 • 上一篇    下一篇

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

苏洁,刘帅,罗智勇,孙广路   

  1. 哈尔滨理工大学计算机科学与技术学院,黑龙江 哈尔滨 150080
  • 出版日期:2016-06-25 发布日期:2017-08-04
  • 基金资助:
    黑龙江省自然科学基金资助项目;黑龙江省教育科学规划课题基金资助项目;黑龙江省普通高等学校新世纪优秀人才培养计划基金资助项目;黑龙江省博士后基金资助项目

Method of constructing an anonymous graph based on information loss estimation

Jie SU,Shuai LIU,Zhi-yong LUO,Guang-lu SUN   

  1. School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China
  • Online:2016-06-25 Published:2017-08-04
  • Supported by:
    The Natural Science Foundation of Heilongjiang Province;Scientific Planning Issues of Education in Heilongjiang Province;Research Fund for the Program of New Century Excellent Talents in Heilongjiang Provincial University;Post Doctoral Fund of Heilongjiang Province

摘要:

首先分析了在进化的社会网络序列中,攻击者利用节点度信息,通过识别目标节点的方法对局部社会网络进行攻击过程,分析了利用k匿名方法对该类攻击进行隐私保护时存在的信息损失问题,针对该问题,提出了一种基于信息损失量估计的k匿名图流构造方法,通过子图节点属性泛化、子图内部结构的泛化控制图重构的信息损失,通过禁止子图内部扰动阻止网络攻击。定义匿名过程中由于图重构造成的节点和结构信息损失的估算方法,建立了基于贪婪聚类算法的网络节点的k匿名聚类算法,根据信息损失估计实现匿名分组,在进化的社会网络中以最小信息损失量构造匿名社会网络,在医疗诊断数据集上的实验表明所提方法能够较理想地控制信息损失量。

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

Abstract:

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.

Key words: social network, privacy protection, k-anonymity, information loss estimation

No Suggested Reading articles found!