一种含敏感关系社会网络隐私保护方法-(k,l)-匿名模型  

A Privacy-preserving Method for Social Networks with Sensitive Relationship-a(k,l)-anonymity Model

作　　者：李静[1] 韩建民[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《小型微型计算机系统》2013年第5期1003-1008,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61170108;6110019)资助;浙江省自然科学基金项目(Y1100161)资助

摘　　要：现有的社会网络隐私保护方法大多是针对社会网络中的个体,不能有效地保护社会网络中的敏感关系.为此,论文提出了一种(k,l)-匿名模型,该模型要求每个含敏感关系结点的敏感关系至少有l个,且要求度相同的结点至少有k个,从而在保护敏感关系的同时,抵制了度攻击.论文还提出了实现(k,l)-匿名模型的贪心算法和动态规划算法.并从度匿名化代价(dDAC)、图的平均最短距离差异(dASP)和图的聚类系数差异(dACC)三个角度对两个算法进行了比较,实验表明在匿名网络的可用性方面,动态规划算法优于贪心算法.Most of the existing privacy preservation methods for social networks focus on protecting individual identities, which cannot protect sensitive relationship effectively. Therefore, the paper proposes a （ k,l）-anonymity model. The model requires that the number of the sensitive edges of a node with sensitive edge is at least l, and that there exist at least k nodes with the same degree. So it not only protects sensitive relationship, but also resists degree attack. The paper also proposes a greedy algorithm and a dynamic programming algorithm to implement the （k, l）-anonymity model and compares the two algorithms from the view of degree anonymization cost, difference of ASP, difference of ACC. Experiments show that in the view of utility of anonymous networks, the DP algorithm is superior to the greedy algorithm.

关 键 词：社会网络 (k l)-匿名模型 敏感关系 隐私保护 

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