Augmentation-Based Edge Differentially Private Path Publishing in Networks

Lu, Zhigang, and Shen, Hong (2022) Augmentation-Based Edge Differentially Private Path Publishing in Networks. IEEE Transactions on Network and Service Management, 19 (4). pp. 5183-5195.

[img] PDF (Published Version) - Published Version
Restricted to Repository staff only

View at Publisher Website:


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.

Item ID: 77404
Item Type: Article (Research - C1)
ISSN: 1932-4537
Copyright Information: © 2022 IEEE.
Date Deposited: 06 Mar 2023 23:06
FoR Codes: 46 INFORMATION AND COMPUTING SCIENCES > 4604 Cybersecurity and privacy > 460402 Data and information privacy @ 100%
SEO Codes: 22 INFORMATION AND COMMUNICATION SERVICES > 2204 Information systems, technologies and services > 220405 Cybersecurity @ 100%
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page