Augmentation-based edge differentially private path publishing in networks

Paths in a given network represent the occurrence sequences of nodes in many real world applications, such as disease transmission chains, object trajectories and data access sequences. In this paper, we address the problem of publishing edge-privacy preserved path information for a single path such that legitimate users with the full knowledge of the network can reconstruct the path with the published information, but not adversaries, even if they have the maximum background knowledge of all the vertices and all edges but one (on the path) of the network. Existing studies on edge privacy against inference attacks focus on publishing either differential privacy (DP) noise injected graph statistics or DP edge perturbed graph topology to achieve edge differential privacy preservation. However, none of them provides an assurance on both edge privacy and data utility. To effectively protect edge privacy and maintain data utility, we propose a novel scheme of DP augmentation instead of DP perturbation as did in existing work, that publishes a simple-topology graph containing an augmented path with fake edges and vertices applying differential privacy to protect the actual path, such that only the legitimate users are able to reconstruct the actual path with high probability. We theoretically analyse the performance of our algorithm in terms of output quality on differential privacy and utility, and execution efficiency. We also conduct extensive experimental evaluations on a high-performance cluster system to validate our analytical results.