Efficient publication of distributed and overlapping graph data under differential privacy

• DOI: 10.26599/tst.2021.9010018
• Publication Date: 2021-09-29T21:05:38Z
• Authors: Xu Zheng; Lizong Zhang; Kaiyang Li; Xi Zeng
• Keywords: Differential Privacy; Graph property; Comparability graph; Null graph

Graph data publication has been considered as an important step for analysis and mining. data, which provide knowledge on interactions among entities, can be locally generated held by distributed owners. These are usually sensitive private, because they may related to owners' personal activities hijacked adversaries conduct inference attacks. Current solutions either consider private graph centralized contents or disregard the overlapping of graphs in manners. Therefore, this work proposes a novel framework publication. In framework, differential privacy is applied justify safety published contents. It includes four phases, i.e., combination, plan construction sharing, perturbation, reconstruction. The selection guided one coordinator, each perturbed carefully with Laplace mechanism. problem formulated proven NP-complete. Then, heuristic algorithm proposed selection. correctness combined all edges analyzed. This study also discusses scenario without coordinator some insights into