改进的k度匿名图构造算法

Improved Algorithm for Constructing k-Degree Anonymous Graphs

在社交网络中,为防范用户隐私泄漏,在用户数据发布前需要做匿名化处理.针对以节点度数为背景知识的隐私攻击,将社交网络匿名化问题建模为图的k度匿名化问题;其主要方法是对图添加尽可能少的边或点来满足度匿名化要求,其中要求添加边或点较少是期望尽可能保持原图结构特性.目前,加边类算法并不能很好地保留平均路径长度等结构特性;加边且可加点类算法尽管能更好地保留原图结构特性,但添加的边或点较多.本文融合两类算法的策略提出改进算法.新算法利用贪心法生成匿名度序列,然后基于社区结构加边,并且优先满足其匿名代价高于平均匿名代价的节点的匿名化要求;若加边不能完成匿名化,则通过加点实现图匿名化.真实数据集上的实验结果表明新算法能更好地保留图的几种典型的结构特性,并且添加的边或点更少.

In social networks,anonymization processing is required to prevent the leakage of user privacy before user data is released.In this study,the social network anonymization is modeled as the k-degree anonymization of graphs given the privacy attack with the background of node degrees.The major method is to add as few edges or nodes as possible to the graph to meet the degree-anonymization requirements,and by doing this,the structural characteristics of the original graph are expected to be maintained to a large extent.At present,the edge-adding algorithms cannot well retain the basic structural characteristics such as the average path length,while the edge-node adding algorithms can better retain the structural characteristics of the original graph after adding many edges or nodes.Considering this situation,this study proposes an improved algorithm combining the two algorithms.Firstly,the greedy algorithm is used to generate the anonymity sequence,and then the edge-adding operation is performed on the basis of the community structure.The anonymization requirements of nodes with higher anonymity costs than the average anonymity costs are satisfied first,and node adding can be applied to the graph when edge adding cannot complete the anonymization.The experimental results of actual datasets show that the new algorithm can better retain several typical structural characteristics of the graph,and the number of added edges or nodes is less.