ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (3): 508-520.doi: 10.7544/issn1000-1239.2019.20170886

• 信息安全 • 上一篇    下一篇



  1. 1(数学工程与先进计算国家重点实验室(中国人民解放军战略支援部队信息工程大学) 郑州 450001); 2(广西密码学与信息安全重点实验室(桂林电子科技大学) 广西桂林 541004) (
  • 出版日期: 2019-03-01
  • 基金资助: 

Graph Degree Histogram Publication Method with Node-Differential Privacy

Zhang Yuxuan1, Wei Jianghong1, Li Ji1, Liu Wenfen2, Hu Xuexian1   

  1. 1(State Key Laboratory of Mathematical Engineering and Advanced Computing (PLA Strategic Support Force Information Engineering University), Zhengzhou 450001); 2(Guangxi Key Laboratory of Cryptography and Information Security (Guilin University of Electronic Technology), Guilin, Guangxi 541004)
  • Online: 2019-03-01

摘要: 社交网络、邮件系统、推荐系统等信息系统的广泛使用产生了大规模的图数据,在点或边差分隐私约束下对这些数据进行发布和共享可以充分发挥其潜在价值,同时又能保证数据中所涉及用户的隐私信息不被泄露.针对点差分隐私定义下查询函数敏感度比较大的问题,提出一种基于度排序的边移除方法(sequence edge-removal, SER),并在此基础上进一步给出了2种点差分隐私下图的度分布直方图发布机制.仿真实验表明:SER方法能有效抑制发布机制的敏感度,保留更多原始图中的边,降低了发布数据与真实数据之间的误差.此外,相比于已有工作,基于SER方法的度直方图发布机制在提供同等隐私保护水平的条件下,更好地刻画了真实数据的度分布,提高了发布数据的可用性.

关键词: 隐私保护, 图数据, 差分隐私, 度分布, 直方图发布

Abstract: The widespread use of various information systems, e.g. social networks, mail systems and recommendation systems, has produced a large amount of graph data. Publishing and sharing these data under the edge or node differential privacy can fully utilize their potential value, meanwhile, the privacy of the involved users can be preserved. Compared with the edge differential privacy, the node differential privacy can effectively prevent users from being re-identified. However, it will lead to a higher sensitivity of the query function at the same time. To conquer this problem, a novel method named sequence edge-removal (SER) is proposed, based on which two graph degree distribution histogram publication mechanisms under node difference privacy are put forward. The experiment results illustrate that the SER method can effectively suppress the sensitivity of the publishing mechanism, and also can retain more edges of the original graph. In addition, it decreases the errors between the published data and the original data. Compared with available works, under the constraint of providing the same level of privacy preservation, the proposed histogram publishing mechanism based on the SER method can describe the degree distribution of the original data more accurately, and thus improves the usability of the published data.

Key words: privacy protection, graph data, differential privacy, degree distribution, histogram publishing