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

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

研究成果: Conference 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.

主出版物標題Multidisciplinary Social Networks Research - 2nd International Conference, MISNC 2015, Proceedings
編輯Kai Wang, Shiro Uesugi, Leon Wang, Koji Okuhara, I-Hsien Ting
發行者Springer Verlag
出版狀態Published - 2015
事件2nd International Conference on Multidisciplinary Social Networks Research, MISNC 2015 - Matsuyama, Japan
持續時間: 2015 9月 12015 9月 3


名字Communications in Computer and Information Science


Other2nd International Conference on Multidisciplinary Social Networks Research, MISNC 2015

All Science Journal Classification (ASJC) codes

  • 電腦科學(全部)
  • 數學(全部)


深入研究「Extending [k1, k2] anonymization of shortest paths for social networks」主題。共同形成了獨特的指紋。