[k1, k2]-anonymization of shortest paths

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Privacy preserving network publishing has been studied extensively in recent years. Although more works have adopted un-weighted graphs to model network relationships, weighted graph modeling can provide deeper analysis of the degree of relationships. Previous works on weighted graph privacy have concentrated on preserving the shortest path characteristic between pairs of vertices. Two common types of privacy have been proposed. One type of privacy tried to add random noise edge weights to the graph but still maintain the same shortest path. The other privacy, k-shortest path privacy, minimally perturbed edge weights so that there exists k shortest paths. However, the k-shortest path privacy only considers anonymizing same fixed number of shortest paths for all pairs of source and destination vertices. In this work, we present a new concept called [k1, k2]-shortest path privacy to allow different number of shortest paths for different pairs of vertices. A published network graph with [k1, k2]-shortest path privacy has at least k' indistinguishable shortest paths between the source and destination vertices, where k1≤k'≤k2. A heuristic algorithm based on modifying only Non-Visited (NV) edges is proposed and experimental results showing the feasibility and characteristics of the proposed approach are presented.

Original languageEnglish
Title of host publication12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014
EditorsYu-Hui Tao, Hsin-Chang Yang, I-Hsien Ting, Matthias Steinbauer, Ismail Khalil, Gabriele Anderst-Kotsis
PublisherAssociation for Computing Machinery, Inc
Pages317-321
Number of pages5
ISBN (Electronic)9781450330084
DOIs
Publication statusPublished - 2014 Dec 8
Event12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014 - Kaohsiung, Taiwan
Duration: 2014 Dec 82014 Dec 10

Publication series

Name12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014

Other

Other12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014
CountryTaiwan
CityKaohsiung
Period14-12-0814-12-10

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Computer Science Applications

Fingerprint Dive into the research topics of '[k<sub>1</sub>, k<sub>2</sub>]-anonymization of shortest paths'. Together they form a unique fingerprint.

Cite this