ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (6): 1352-1364.doi: 10.7544/issn1000-1239.2016.20140695

• 信息处理 • 上一篇    下一篇

增量的动态社会网络匿名化技术

郭彩华,王斌,朱怀杰,杨晓春   

  1. (东北大学信息科学与工程学院 沈阳 110004) (zhuhjneu@gmail.com)
  • 出版日期: 2016-06-01
  • 基金资助: 
    国家“九七三”重点基础研究发展计划基金项目(2012CB316201);国家自然科学基金项目(61173031,61272178);国家自然科学基金海外及港澳学者合作基金项目(61129002);高等学校博士学科点专项科研基金项目(20110042110028);中央高校基本科研业务费专项资金项目(N120504001)

Incremental Dynamic Social Network Anonymity Technology

Guo Caihua, Wang Bin, Zhu Huaijie, Yang Xiaochun   

  1. (College of Information Science and Engineering, Northeastern University, Shenyang 110004)
  • Online: 2016-06-01

摘要: 随着社会网络的快速发展和普及,如何保护社会网络中的敏感信息已成为当前数据隐私保护研究领域的热点问题.对此,近年来出现了多种社会网络匿名化技术. 现有的匿名技术大多把社会网络抽象成简单图,然而实际生活中存在大量增量变化的社会网络,例如email通信网络,简单图并不能很好地刻画这种增量变化,因此,将社会网络抽象成增量序列具有现实意义.同时,在实际生活中大部分网络是带有权重信息的,即很多社会网络以加权图的形式出现,加权图与简单图相比携带了更多社会网络中的信息,也会带来更多的隐私泄露. 将增量的动态社会网络抽象成一个加权图的增量序列. 为了匿名加权图增量序列,提出了加权图增量序列k-匿名隐私保护模型,并设计了基于权重链表的baseline匿名算法WLKA和基于超图的匿名算法HVKA来防止基于结点标签和权重链表的攻击. 最后,通过在真实数据集上的大量测试,证明了WLKA算法能够保证加权图增量序列隐私保护的有效性,HVKA算法则在WLKA的基础上更好地保留了原图的结构性质并提高了权重信息的可用性,同时还降低了匿名过程的时间代价.

关键词: 动态社会网络, 增量序列, 数据隐私, 权重链表, 超图, 信息损失

Abstract: With the rapid development and popularity of social networks, how to protect privacy in social networks has become a hot topic in the realm of data privacy. However, in most of existing anonymity technologies in recent years, the social network is abstracted into a simple graph. In fact, there are a lot of incremental changes of social networks in real life and a simple graph can not reflect incremental society network well, so abstracting the social network into the incremental sequences becomes more realistic. Meanwhile, in real life most of the network contains weight information, that is, a lot of social networks are weighted graphs. Compared with the simple graph, weighted graphs carry more information of the social network and will leak more privacy. In this paper, incremental dynamic social network is abstracted into a weighted graph incremental sequence. In order to anonymize weighted graph incremental sequence, we propose a weighted graph incremental sequence k-anonymous privacy protection model, and design a baseline anonymity algorithm (called WLKA) based on weight list and HVKA algorithm based on hypergraph, which prevents the attacks from node point labels and weight packages. Finally, through a lot of tests on real data sets, it proves that WLKA can guarantee the validity of the privacy protection on weighted graph incremental sequence. Compared with WLKA, HVKA is better to retain the original structure properties and improves the availability of weight information, but it also reduces the time cost of anonymous process.

Key words: dynamic social network, incremental sequence, data privacy, weight list, hypergraph, loss of information

中图分类号: