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

利用传统的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%以上.所提方法在有效保证隐私的基础上,可以显著的降低对原始图结构信息的改变.

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

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 by 17.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.