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

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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

Cite this