摘要： 针对加权网络数据未经处理发布会造成最短路径隐私泄露的问题,提出k-最短路径候选匿名隐私保护模型,并给出一种最短路径贪心泛化算法实现该匿名模型。对目标节点对之间的top-k路径上的权重进行泛化,根据候选匿名区间调整top-k路径与最短路径不重叠边的泛化区
间,使得目标节点对之间存在k个最短路径的候选集,攻击者不能以高于1/k的概率识别最短路径。实验结果表明,提出算法的边权重分布变化量、查询错误率和累积误差明显小于k-可能路径匿名算法和k-多样化路径匿名算法,在不改变图结构特征的同时能有效实现最短路径
匿名。
关键词:
社交网络,
隐私保护,
最短路径,
k匿名,
泛化,
边权重
Abstract: 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 k-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.
Key words:
social network,
privacy preserving,
shortest path,
k-anonymity,
generalization,
edge weight
中图分类号: