点差分隐私下基于度序列的图生成模型

Graph Generation Model Based on Degree Sequence with Node-Differential Privacy

随着社交网络技术的快速发展,图数据的隐私保护已经成为大数据研究领域的热点问题之一。差分隐私的合成图生成技术在对图数据的隐私泄露风险进行严格地量化表示的同时,能够有效地保证图数据的可用性。针对现有算法隐私保障性较弱、查询函数敏感度较大等问题,利用图投影方法降低敏感度,提出一种新的点差分隐私下基于度序列的合成图生成算法。首先利用图投影方法将原有图数据进行压缩,基于dK模型捕获压缩图结构对应的2K序列;然后将2K序列聚类成多个连续且互不相交的子序列,再分别进行加噪;最后根据整合后的新2K序列生成满足差分隐私的社交网络发布图。实验比较表明,所提方案在保证较强隐私保护性的同时,提高了发布数据的准确性和可用性。

With the rapid development of social network technology,the privacy protection of graph data has become one of the hot issues in the field of big data research.The differential privacy synthetic graph generation technology can strictly guarantee the availability of graph data while strictly quantifying the privacy risk of graph data.To address the problems of the weak privacy guarantee of the existing algorithms and the high sensitivity of the query function,a graph projection method is used to reduce the sensitivity,and a new synthetic graph generation algorithm based on degree sequence with node-differential privacy is proposed.First,the original projection data is compressed using the graph projection method,and the 2K sequence corresponding to the compressed graph structure is captured based on the dK model;then the 2K sequence is clustered into multiple continuous and disjoint subsequences,and noise is added separately;the integrated new 2K sequence generates a social network release graph that satisfies differential privacy.Experimental comparisons show that the proposed scheme improves the accuracy and usability of published data while ensuring strong privacy protection.