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


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
Number of pages13
ISBN (Print)9783662483183
Publication statusPublished - 2015
Event2nd International Conference on Multidisciplinary Social Networks Research, MISNC 2015 - Matsuyama, Japan
Duration: 2015 Sept 12015 Sept 3

Publication series

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


Other2nd International Conference on Multidisciplinary Social Networks Research, MISNC 2015

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'Extending [k1, k2] anonymization of shortest paths for social networks'. Together they form a unique fingerprint.

Cite this