Edge types vs privacy in K-anonymization of shortest paths

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

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


Information breaches in social networks and other published data have caused many concerns of privacy issues in recent years. Since information in networks can be modeled as graphs, various techniques have been proposed to preserve privacy of sensitive data on directed/un-directed, weighted/un-weighted graphs. To preserve privacy on graphs, most works for publishing anonymized social networks have attempted to prevent unique patterns to be re-identified, such as, nodes, links, and sub-graphs. In this work, we study the problem of anonymizing sensitive shortest paths in graphs. We examine the concept of k-shortest path privacy, in which at least k indistinguishable shortest paths exist between specified sensitive source and destination vertices. Due to the overlaps of shortest paths, we propose three algorithms to modify three categories of edges to achieve the k-shortest path privacy. Numerical experiments showing the characteristics of the proposed algorithms are given. The results demonstrate that the proposed algorithms are all feasible to achieve k-shortest path privacy, with different degrees of execution times and information losses, and can be served as design reference for shortest path anonymization.

Original languageEnglish
Pages (from-to)348-359
Number of pages12
JournalApplied Soft Computing Journal
Publication statusPublished - 2015 Jun 1

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Edge types vs privacy in K-anonymization of shortest paths'. Together they form a unique fingerprint.

Cite this