匿名最短路径的top-k路径贪心泛化算法
|
摘要
针对加权网络数据未经处理发布会造成最短路径隐私泄露的问题,提出k-最短路径候选匿名隐私保护模型,并给出一种最短路径贪心泛化算法实现该匿名模型。对目标节点对之间的top-k路径上的权重进行泛化,根据候选匿名区间调整top-k路径与最短路径不重叠边的泛化区间,使得目标节点对之间存在k个最短路径的候选集,攻击者不能以高于1/k的概率识别最短路径。实验结果表明,提出算法的边权重分布变化量、查询错误率和累积误差明显小于k-可能路径匿名算法和k-多样化路径匿名算法,在不改变图结构特征的同时能有效实现最短路径匿名。
With the development of social networks,the issues of privacy preservation arouse extensive attention.It can cause privacy disclosure of the shortest path if weighted social network data are protected before its publication.In order to solve this issue,this paper proposes a A:-shortest paths candidate anonymity model and develops a shortest path greedy generalization based algorithm to achieve this model.A generalization is made on the weight of top-k path of target nodes.The generalization interval of non-overlapping edges between shortest paths and top-k paths is adjusted,according to the candidate anonymous interval.There are k shortest paths between target nodes,which limit the probability of shortest path being re-identified to 1/k.Experimental results demonstrate that the change of edge weight distribution/error rates for query and error accumulation of the proposed algorithm are significantly less than k-possible path anonymity algorithm and k-multiple path anonymity algorithm.The proposed algorithm can effectively achieve shortest path anonymity.Meanwhile,it can keep the structure of graph not being changed.
With the development of social networks,the issues of privacy preservation arouse extensive attention.It can cause privacy disclosure of the shortest path if weighted social network data are protected before its publication.In order to solve this issue,this paper proposes a A:-shortest paths candidate anonymity model and develops a shortest path greedy generalization based algorithm to achieve this model.A generalization is made on the weight of top-k path of target nodes.The generalization interval of non-overlapping edges between shortest paths and top-k paths is adjusted,according to the candidate anonymous interval.There are k shortest paths between target nodes,which limit the probability of shortest path being re-identified to 1/k.Experimental results demonstrate that the change of edge weight distribution/error rates for query and error accumulation of the proposed algorithm are significantly less than k-possible path anonymity algorithm and k-multiple path anonymity algorithm.The proposed algorithm can effectively achieve shortest path anonymity.Meanwhile,it can keep the structure of graph not being changed.
引文
[1]Zhou Bin,Jian Pei.A Brief Survey on Anonymization Techniques for Privacy Preserving Publishing of Social Network Data[J].ACM SIGKDD Explorations Newsletter,2008,10(2):12-22.
[2]兰丽辉,鞠时光,金华.社会网络数据的k-匿名发布[J].计算机科学,2011,38(11):156-160.
[3]Liu Lian,Wang Jie,Liu Jinze,et al.Privacy Preserving in Social Networks Against Sensitive Edge Disclosure,CMIDA-Hi PSCCS 006-08[R].Department of Computer Science,University of Kentucky,2008.
[4]Campan A,Truta T M.AClustering Approach for Data and Structural Anonymity in Social Networks[C]//Proceedings of ACM SIGMOD International Conference on Privacy Security.New York,USA:ACM Press,2008:93-104.
[5]Liu Kun,Terzi E.Towards Identity Anonymization on Graphs[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2008:93-106.
[6]Ada J,Liu Jia.K-Isomorphism:Privacy Preserving Network Publication Against Structural Attacks[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2010:459-470.
[7]Li Yidong,Shen Hong.Anonymizing Graphs Against Weightbased Attacks[C]//Proceedings of IEEE Inter-national Conference on Data Mining.Washington D.C.,USA:IEEE Press,2010:491-498.
[8]Liu Xiangyu,Yang Xiaochun.A Generalization Based Approach for Anonymizing Weighted Social Network Graphs[C]//Proceedings of IEEE International Conference on Web-age Information Management.Washington D.C.,USA:IEEE Press,2011:118-130.
[9]刘华玲,郑建国,孙辞海.基于贪心扰动的社交网络隐私保护研究[J].电子学报,2013:41(8):1586-1591.
[10]Das S,Egecioglu O,Abbadi A E.Anonymizing Weighted Social Network Graphs[C]//Proceedings of the 26th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2010:904-907.
[11]刘向宇,王斌,杨晓春.社会网络数据发布隐私保护技术综述[J].软件学报,2014,25(3):576-590.
[12]Tsai Yu-Chuan,Wang Shyue-Liang,Kao Hung-Yu,et al.Confining Edge Types in K-anonymization of Shortest Paths[C]//Proceedings of IEEE International Conference on Innovations in Bio-inspired Computing and Application.Washington D.C.,USA:IEEE Press,2012:318-322.
[13]陈可,刘向宇,王斌,等.防止路径攻击的加权社会网络匿名化技术[J].计算机科学与探索,2013,7(11):961-972.
[14]Wang Liang,Zhengze.Anonymizing Shortest Paths on Social Network Graphs[C]//Proceedings of the 3rd Intelligent Conference on Intelligent Information and Database Systems.Berlin,Germany:Springer,2011:129-136.
[2]兰丽辉,鞠时光,金华.社会网络数据的k-匿名发布[J].计算机科学,2011,38(11):156-160.
[3]Liu Lian,Wang Jie,Liu Jinze,et al.Privacy Preserving in Social Networks Against Sensitive Edge Disclosure,CMIDA-Hi PSCCS 006-08[R].Department of Computer Science,University of Kentucky,2008.
[4]Campan A,Truta T M.AClustering Approach for Data and Structural Anonymity in Social Networks[C]//Proceedings of ACM SIGMOD International Conference on Privacy Security.New York,USA:ACM Press,2008:93-104.
[5]Liu Kun,Terzi E.Towards Identity Anonymization on Graphs[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2008:93-106.
[6]Ada J,Liu Jia.K-Isomorphism:Privacy Preserving Network Publication Against Structural Attacks[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2010:459-470.
[7]Li Yidong,Shen Hong.Anonymizing Graphs Against Weightbased Attacks[C]//Proceedings of IEEE Inter-national Conference on Data Mining.Washington D.C.,USA:IEEE Press,2010:491-498.
[8]Liu Xiangyu,Yang Xiaochun.A Generalization Based Approach for Anonymizing Weighted Social Network Graphs[C]//Proceedings of IEEE International Conference on Web-age Information Management.Washington D.C.,USA:IEEE Press,2011:118-130.
[9]刘华玲,郑建国,孙辞海.基于贪心扰动的社交网络隐私保护研究[J].电子学报,2013:41(8):1586-1591.
[10]Das S,Egecioglu O,Abbadi A E.Anonymizing Weighted Social Network Graphs[C]//Proceedings of the 26th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2010:904-907.
[11]刘向宇,王斌,杨晓春.社会网络数据发布隐私保护技术综述[J].软件学报,2014,25(3):576-590.
[12]Tsai Yu-Chuan,Wang Shyue-Liang,Kao Hung-Yu,et al.Confining Edge Types in K-anonymization of Shortest Paths[C]//Proceedings of IEEE International Conference on Innovations in Bio-inspired Computing and Application.Washington D.C.,USA:IEEE Press,2012:318-322.
[13]陈可,刘向宇,王斌,等.防止路径攻击的加权社会网络匿名化技术[J].计算机科学与探索,2013,7(11):961-972.
[14]Wang Liang,Zhengze.Anonymizing Shortest Paths on Social Network Graphs[C]//Proceedings of the 3rd Intelligent Conference on Intelligent Information and Database Systems.Berlin,Germany:Springer,2011:129-136.