Augmentation-Based Edge Differentially Private Path Publishing in Networks
Journal Publication ResearchOnline@JCUAbstract
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.
Journal
IEEE Transactions on Network and Service Management
Publication Name
N/A
Volume
19
ISBN/ISSN
1932-4537
Edition
N/A
Issue
4
Pages Count
13
Location
N/A
Publisher
Institute of Electrical and Electronics Engineers
Publisher Url
N/A
Publisher Location
N/A
Publish Date
N/A
Url
N/A
Date
N/A
EISSN
N/A
DOI
10.1109/TNSM.2022.3182864