Edge types vs privacy in K-anonymization of shortest paths

被引:7
作者
Tsai, Yu-Chuan [1 ]
Wang, Shyue-Liang [2 ,4 ]
Kao, Hung-Yu [1 ]
Hong, Tzung-Pei [3 ]
机构
[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 70101, Taiwan
[2] Natl Univ Kaohsiung, Dept Informat Management, Kaohsiung 81148, Taiwan
[3] Natl Univ Kaohsiung, Dept Comp Sci & Informat Engn, Kaohsiung 81148, Taiwan
[4] ACIIDS, Bangkok, Thailand
关键词
Social networks; Privacy preservation; Shortest path; Anonymity; k-Shortest path privacy; SOCIAL NETWORKS; PROTECTION;
D O I
10.1016/j.asoc.2015.03.005
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Information breaches in social networks and other published data have caused many concerns of privacy issues in recent years. Since information in networks can be modeled as graphs, various techniques have been proposed to preserve privacy of sensitive data on directed/un-directed, weighted/un-weighted graphs. To preserve privacy on graphs, most works for publishing anonymized social networks have attempted to prevent unique patterns to be re-identified, such as, nodes, links, and sub-graphs. In this work, we study the problem of anonymizing sensitive shortest paths in graphs. We examine the concept of k-shortest path privacy, in which at least k indistinguishable shortest paths exist between specified sensitive source and destination vertices. Due to the overlaps of shortest paths, we propose three algorithms to modify three categories of edges to achieve the k-shortest path privacy. Numerical experiments showing the characteristics of the proposed algorithms are given. The results demonstrate that the proposed algorithms are all feasible to achieve k-shortest path privacy, with different degrees of execution times and information losses, and can be served as design reference for shortest path anonymization. (C) 2015 Elsevier B.V. All rights reserved.
引用
收藏
页码:348 / 359
页数:12
相关论文
共 41 条
  • [1] [Anonymous], 2006, FREEDOM INFORM WORLD
  • [2] [Anonymous], 2009, Proceedings of the SIAM International Conference on Data Mining, SDM'09
  • [3] [Anonymous], 2007, P 16 INT C WORLD WID
  • [4] [Anonymous], 2008, Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data
  • [5] Barbaro MichaelTom Zeller Jr., 2006, A Face Is Exposed for AOL Searcher No. 4417749
  • [6] Bhagat S., 2009, P VLDB ENDOW, V2, P766, DOI DOI 10.14778/1687627.1687714
  • [7] A comparison of clustering-based privacy-preserving collaborative filtering schemes
    Bilge, Alper
    Polat, Huseyin
    [J]. APPLIED SOFT COMPUTING, 2013, 13 (05) : 2478 - 2489
  • [8] Charanyaa S., 2014, INT J ADV RES COMPUT, V3, P5722
  • [9] Cheng J., 2010, P 2010 ACM SIGMOD IN, P459, DOI DOI 10.1145/1807167.1807218
  • [10] Costa C, 2010, PC MAGAZINE