基于节点1-邻居图相似性的社会网络匿名技术

Social Network Data Anonymization Based on Node 1-neighbor Graphs Similarity

利用传统的k匿名技术在社会网络中进行隐私保护时会存在聚类准则单一、图中数据信息利用不足等问题.针对该问题,提出了一种利用Kullback-Leibler(KL)散度衡量节点1-邻居图相似性的匿名技术(anonymization techniques for measuring the similarity of node 1-neighbor graph based on Kullback-Leibler divergence,SNKL).根据节点1-邻居图分布的相似性对原始图节点集进行划分,按照划分好的类进行图修改,使修改后的图满足k匿名,完成图的匿名发布.实验结果表明,SNKL方法与HIGA方法相比在聚类系数上的改变量平均降低了17.3%,同时生成的匿名图与原始图重要性节点重合度保持在95%以上.所提方法在有效保证隐私的基础上,可以显著的降低对原始图结构信息的改变.

Using traditional k-anonymization techniques to achieve privacy protection in social networks is faced with problems such as single clustering criterion and under-utilization of data and information in the graph.To solve this problem,this study proposes an anonymization technique measuring the similarity of the node 1-neighbor graph based on the Kullback-Leibler divergence(SNKL).The original graph node set is divided according to the similarity of node 1-neighbor graph distribution,and the graph is modified according to the divided classes so that the modified graph satisfies k-anonymity.On this basis,the anonymous release of the graph is implemented.The experimental results show that compared with the HIGA method,the SNKL method reduces the amount of change in the clustering coefficients by17.3%on average.Moreover,the overlap ratio between the importance nodes of the generated anonymous graph and those of the original graph is maintained at more than 95%.In addition to protecting privacy effectively,the proposed method can significantly reduce the changes brought to the structural information in the original graph.