k- -anonymization of multiple shortest paths

Shyue Liang Wang, Yu Chuan Tsai, Tzung Pei Hong, Hung Yu Kao

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


The preservation of privacy on information networks has been studied extensively in recent years. Although early work concentrated on preserving sensitive node information and link information to prevent re-identification attacks, recent development has instigated a focus on preserving sensitive edge weight information such as shortest paths. Two types of privacy on edge weights have been proposed. One type of privacy attempts to add random noise edge weights to the graph while still maintaining the same shortest path. The other type of privacy, k-shortest path privacy, minimally perturbs edge weights so that there are at least k shortest paths. However, there might be insufficient paths that can be modified to the same path length. In this work, we present a new concept, called k--shortest path privacy, to allow anonymizing different numbers of shortest paths for different sources and destination vertex pairs. For a given privacy level k and a pair of source and destination vertices with ki paths between the two vertices, we propose a greedy-based algorithm trying to modify Never-Visited, Partially-Visited, and All-Visited edges, in sequence, from top- k shortest paths (or ki available paths) so that all possess the same path length after modification. We use the weighted-proportional-based strategy to modify the edge weights. We also define a new privacy value to quantify the privacy level of k--shortest path privacy. Numerical experiments showing the characteristics of the proposed algorithm are given. Comparison to k-shortest path privacy demonstrates that the proposed approach is more efficient and flexible than the previous model.

Original languageEnglish
Pages (from-to)4215-4226
Number of pages12
JournalSoft Computing
Issue number15
Publication statusPublished - 2017 Aug 1

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Geometry and Topology

Fingerprint Dive into the research topics of 'k<sup>-</sup> -anonymization of multiple shortest paths'. Together they form a unique fingerprint.

Cite this