Extending [k1, k2] anonymization of shortest paths for social networks

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

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

Abstract

Privacy is a great concern when information are published and shared. Privacy-preserving social network data publishing has been studied extensively in recent years. Early works had concentrated on protecting sensitive nodes and links information to prevent privacy breaches. Recent studies start to focus on preserving sensitive edge weight information such as shortest paths. Two types of privacy on sensitive shortest paths 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 at least k shortest paths. However, there might be insufficient paths that can be modified to the same path length. In this work, we extend previously proposed [k1, k2]-shortest path privacy, k1≦k≦k2, to not only anonymizing different number of shortest paths for different source and destination vertex pair, but also modifying different types of edges, such as partially visited edges. Numerical experiments showing the characteristics of the proposed algorithm is given. The proposed algorithm is more efficient in running time than the previous work with similar perturbed ratios of edges.

Original languageEnglish
Title of host publicationMultidisciplinary Social Networks Research - 2nd International Conference, MISNC 2015, Proceedings
EditorsKai Wang, Shiro Uesugi, Leon Wang, Koji Okuhara, I-Hsien Ting
PublisherSpringer Verlag
Pages187-199
Number of pages13
ISBN (Print)9783662483183
DOIs
Publication statusPublished - 2015 Jan 1
Event2nd International Conference on Multidisciplinary Social Networks Research, MISNC 2015 - Matsuyama, Japan
Duration: 2015 Sep 12015 Sep 3

Publication series

NameCommunications in Computer and Information Science
Volume540
ISSN (Print)1865-0929

Other

Other2nd International Conference on Multidisciplinary Social Networks Research, MISNC 2015
CountryJapan
CityMatsuyama
Period15-09-0115-09-03

Fingerprint

Shortest path
Social Networks
Privacy
Experiments
Random Noise
Privacy Preserving
Path Length
Vertex of a graph
Numerical Experiment
Path
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Cite this

Tsai, Y. C., Wang, S. L., Hong, T. P., & Kao, H-Y. (2015). Extending [k1, k2] anonymization of shortest paths for social networks. In K. Wang, S. Uesugi, L. Wang, K. Okuhara, & I-H. Ting (Eds.), Multidisciplinary Social Networks Research - 2nd International Conference, MISNC 2015, Proceedings (pp. 187-199). (Communications in Computer and Information Science; Vol. 540). Springer Verlag. https://doi.org/10.1007/978-3-662-48319-0_15
Tsai, Yu Chuan ; Wang, Shyue Liang ; Hong, Tzung Pei ; Kao, Hung-Yu. / Extending [k1, k2] anonymization of shortest paths for social networks. Multidisciplinary Social Networks Research - 2nd International Conference, MISNC 2015, Proceedings. editor / Kai Wang ; Shiro Uesugi ; Leon Wang ; Koji Okuhara ; I-Hsien Ting. Springer Verlag, 2015. pp. 187-199 (Communications in Computer and Information Science).
@inproceedings{7a84bac845234b93953d1aacd9d938a0,
title = "Extending [k1, k2] anonymization of shortest paths for social networks",
abstract = "Privacy is a great concern when information are published and shared. Privacy-preserving social network data publishing has been studied extensively in recent years. Early works had concentrated on protecting sensitive nodes and links information to prevent privacy breaches. Recent studies start to focus on preserving sensitive edge weight information such as shortest paths. Two types of privacy on sensitive shortest paths 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 at least k shortest paths. However, there might be insufficient paths that can be modified to the same path length. In this work, we extend previously proposed [k1, k2]-shortest path privacy, k1≦k≦k2, to not only anonymizing different number of shortest paths for different source and destination vertex pair, but also modifying different types of edges, such as partially visited edges. Numerical experiments showing the characteristics of the proposed algorithm is given. The proposed algorithm is more efficient in running time than the previous work with similar perturbed ratios of edges.",
author = "Tsai, {Yu Chuan} and Wang, {Shyue Liang} and Hong, {Tzung Pei} and Hung-Yu Kao",
year = "2015",
month = "1",
day = "1",
doi = "10.1007/978-3-662-48319-0_15",
language = "English",
isbn = "9783662483183",
series = "Communications in Computer and Information Science",
publisher = "Springer Verlag",
pages = "187--199",
editor = "Kai Wang and Shiro Uesugi and Leon Wang and Koji Okuhara and I-Hsien Ting",
booktitle = "Multidisciplinary Social Networks Research - 2nd International Conference, MISNC 2015, Proceedings",
address = "Germany",

}

Tsai, YC, Wang, SL, Hong, TP & Kao, H-Y 2015, Extending [k1, k2] anonymization of shortest paths for social networks. in K Wang, S Uesugi, L Wang, K Okuhara & I-H Ting (eds), Multidisciplinary Social Networks Research - 2nd International Conference, MISNC 2015, Proceedings. Communications in Computer and Information Science, vol. 540, Springer Verlag, pp. 187-199, 2nd International Conference on Multidisciplinary Social Networks Research, MISNC 2015, Matsuyama, Japan, 15-09-01. https://doi.org/10.1007/978-3-662-48319-0_15

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

Multidisciplinary Social Networks Research - 2nd International Conference, MISNC 2015, Proceedings. ed. / Kai Wang; Shiro Uesugi; Leon Wang; Koji Okuhara; I-Hsien Ting. Springer Verlag, 2015. p. 187-199 (Communications in Computer and Information Science; Vol. 540).

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

TY - GEN

T1 - Extending [k1, k2] anonymization of shortest paths for social networks

AU - Tsai, Yu Chuan

AU - Wang, Shyue Liang

AU - Hong, Tzung Pei

AU - Kao, Hung-Yu

PY - 2015/1/1

Y1 - 2015/1/1

N2 - Privacy is a great concern when information are published and shared. Privacy-preserving social network data publishing has been studied extensively in recent years. Early works had concentrated on protecting sensitive nodes and links information to prevent privacy breaches. Recent studies start to focus on preserving sensitive edge weight information such as shortest paths. Two types of privacy on sensitive shortest paths 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 at least k shortest paths. However, there might be insufficient paths that can be modified to the same path length. In this work, we extend previously proposed [k1, k2]-shortest path privacy, k1≦k≦k2, to not only anonymizing different number of shortest paths for different source and destination vertex pair, but also modifying different types of edges, such as partially visited edges. Numerical experiments showing the characteristics of the proposed algorithm is given. The proposed algorithm is more efficient in running time than the previous work with similar perturbed ratios of edges.

AB - Privacy is a great concern when information are published and shared. Privacy-preserving social network data publishing has been studied extensively in recent years. Early works had concentrated on protecting sensitive nodes and links information to prevent privacy breaches. Recent studies start to focus on preserving sensitive edge weight information such as shortest paths. Two types of privacy on sensitive shortest paths 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 at least k shortest paths. However, there might be insufficient paths that can be modified to the same path length. In this work, we extend previously proposed [k1, k2]-shortest path privacy, k1≦k≦k2, to not only anonymizing different number of shortest paths for different source and destination vertex pair, but also modifying different types of edges, such as partially visited edges. Numerical experiments showing the characteristics of the proposed algorithm is given. The proposed algorithm is more efficient in running time than the previous work with similar perturbed ratios of edges.

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

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

U2 - 10.1007/978-3-662-48319-0_15

DO - 10.1007/978-3-662-48319-0_15

M3 - Conference contribution

AN - SCOPUS:84946051238

SN - 9783662483183

T3 - Communications in Computer and Information Science

SP - 187

EP - 199

BT - Multidisciplinary Social Networks Research - 2nd International Conference, MISNC 2015, Proceedings

A2 - Wang, Kai

A2 - Uesugi, Shiro

A2 - Wang, Leon

A2 - Okuhara, Koji

A2 - Ting, I-Hsien

PB - Springer Verlag

ER -

Tsai YC, Wang SL, Hong TP, Kao H-Y. Extending [k1, k2] anonymization of shortest paths for social networks. In Wang K, Uesugi S, Wang L, Okuhara K, Ting I-H, editors, Multidisciplinary Social Networks Research - 2nd International Conference, MISNC 2015, Proceedings. Springer Verlag. 2015. p. 187-199. (Communications in Computer and Information Science). https://doi.org/10.1007/978-3-662-48319-0_15