[k1, k2]-anonymization of shortest paths

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

研究成果: Conference contribution

摘要

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.

原文English
主出版物標題12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014
編輯Yu-Hui Tao, Hsin-Chang Yang, I-Hsien Ting, Matthias Steinbauer, Ismail Khalil, Gabriele Anderst-Kotsis
發行者Association for Computing Machinery, Inc
頁面317-321
頁數5
ISBN(電子)9781450330084
DOIs
出版狀態Published - 2014 十二月 8
事件12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014 - Kaohsiung, Taiwan
持續時間: 2014 十二月 82014 十二月 10

出版系列

名字12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014

Other

Other12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014
國家Taiwan
城市Kaohsiung
期間14-12-0814-12-10

    指紋

All Science Journal Classification (ASJC) codes

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

引用此

Tsai, Y. C., Wang, S. L., Hong, T. P., & Kao, H. Y. (2014). [k1, k2]-anonymization of shortest paths. 於 Y-H. Tao, H-C. Yang, I-H. Ting, M. Steinbauer, I. Khalil, & G. Anderst-Kotsis (編輯), 12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014 (頁 317-321). (12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014). Association for Computing Machinery, Inc. https://doi.org/10.1145/2684103.2684160