Graph Degree Histogram Publication Method with Node-Differential Privacy

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.