[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

Fingerprint

Heuristic algorithms

All Science Journal Classification (ASJC) codes

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

Cite this

Tsai, Y. C., Wang, S. L., Hong, T. P., & Kao, H-Y. (2014). [k1, k2]-anonymization of shortest paths. In Y-H. Tao, H-C. Yang, I-H. Ting, M. Steinbauer, I. Khalil, & G. Anderst-Kotsis (Eds.), 12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014 (pp. 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
Tsai, Yu Chuan ; Wang, Shyue Liang ; Hong, Tzung Pei ; Kao, Hung-Yu. / [k1, k2]-anonymization of shortest paths. 12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014. editor / Yu-Hui Tao ; Hsin-Chang Yang ; I-Hsien Ting ; Matthias Steinbauer ; Ismail Khalil ; Gabriele Anderst-Kotsis. Association for Computing Machinery, Inc, 2014. pp. 317-321 (12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014).
@inproceedings{5dec5bf230224ad9afb069bb21070d56,
title = "[k1, k2]-anonymization of shortest paths",
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.",
author = "Tsai, {Yu Chuan} and Wang, {Shyue Liang} and Hong, {Tzung Pei} and Hung-Yu Kao",
year = "2014",
month = "12",
day = "8",
doi = "10.1145/2684103.2684160",
language = "English",
series = "12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014",
publisher = "Association for Computing Machinery, Inc",
pages = "317--321",
editor = "Yu-Hui Tao and Hsin-Chang Yang and I-Hsien Ting and Matthias Steinbauer and Ismail Khalil and Gabriele Anderst-Kotsis",
booktitle = "12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014",

}

Tsai, YC, Wang, SL, Hong, TP & Kao, H-Y 2014, [k1, k2]-anonymization of shortest paths. in Y-H Tao, H-C Yang, I-H Ting, M Steinbauer, I Khalil & G Anderst-Kotsis (eds), 12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014. 12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014, Association for Computing Machinery, Inc, pp. 317-321, 12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014, Kaohsiung, Taiwan, 14-12-08. https://doi.org/10.1145/2684103.2684160

[k1, k2]-anonymization of shortest paths. / Tsai, Yu Chuan; Wang, Shyue Liang; Hong, Tzung Pei; Kao, Hung-Yu.

12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014. ed. / Yu-Hui Tao; Hsin-Chang Yang; I-Hsien Ting; Matthias Steinbauer; Ismail Khalil; Gabriele Anderst-Kotsis. Association for Computing Machinery, Inc, 2014. p. 317-321 (12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014).

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

TY - GEN

T1 - [k1, k2]-anonymization of shortest paths

AU - Tsai, Yu Chuan

AU - Wang, Shyue Liang

AU - Hong, Tzung Pei

AU - Kao, Hung-Yu

PY - 2014/12/8

Y1 - 2014/12/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84942515845&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84942515845&partnerID=8YFLogxK

U2 - 10.1145/2684103.2684160

DO - 10.1145/2684103.2684160

M3 - Conference contribution

AN - SCOPUS:84942515845

T3 - 12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014

SP - 317

EP - 321

BT - 12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014

A2 - Tao, Yu-Hui

A2 - Yang, Hsin-Chang

A2 - Ting, I-Hsien

A2 - Steinbauer, Matthias

A2 - Khalil, Ismail

A2 - Anderst-Kotsis, Gabriele

PB - Association for Computing Machinery, Inc

ER -

Tsai YC, Wang SL, Hong TP, Kao H-Y. [k1, k2]-anonymization of shortest paths. In Tao Y-H, Yang H-C, Ting I-H, Steinbauer M, Khalil I, Anderst-Kotsis G, editors, 12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014. Association for Computing Machinery, Inc. 2014. p. 317-321. (12th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2014). https://doi.org/10.1145/2684103.2684160