ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2019, Vol. 56 ›› Issue (3): 508-520.doi: 10.7544/issn1000-1239.2019.20170886

Previous Articles     Next Articles

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

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

CLC Number: