TY - JOUR
T1 - Edge types vs privacy in K-anonymization of shortest paths
AU - Tsai, Yu Chuan
AU - Wang, Shyue Liang
AU - Kao, Hung Yu
AU - Hong, Tzung Pei
N1 - Funding Information:
This work was supported in part by the National Science Council, Taiwan , under grant NSC-100-2221-E-390-030 .
Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2015/6/1
Y1 - 2015/6/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84926218544&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84926218544&partnerID=8YFLogxK
U2 - 10.1016/j.asoc.2015.03.005
DO - 10.1016/j.asoc.2015.03.005
M3 - Article
AN - SCOPUS:84926218544
SN - 1568-4946
VL - 31
SP - 348
EP - 359
JO - Applied Soft Computing Journal
JF - Applied Soft Computing Journal
ER -