Journal of Frontiers of Computer Science and Technology ›› 2013, Vol. 7 ›› Issue (11): 961-972.DOI: 10.3778/j.issn.1673-9418.1305051

Previous Articles     Next Articles

Anonymizing Weighted Social Network Graph against Path-Based Attack

CHEN Ke1, LIU Xiangyu1, WANG Bin1, ZHANG Hongyi2, YANG Xiaochun1+   

  1. 1. College of Information Science and Engineering, Northeastern University, Shenyang 110819, China
    2. International School of Software, Wuhan University, Wuhan 430079, China
  • Online:2013-11-01 Published:2013-11-04

防止路径攻击的加权社会网络匿名化技术

陈  可1,刘向宇1,王  斌1,张弘毅2,杨晓春1+   

  1. 1. 东北大学 信息科学与工程学院,沈阳 110819
    2. 武汉大学 国际软件学院,武汉 430079

Abstract: With the popularity of social networks, data privacy preserving in social networks has become a hot issue among scholars. Since the broad privacy information, an adversary can use a variety of background knowledge to attack against privacy. Most of the present technology on privacy preservation can deal with simple graphs only, and cannot be applied to weighted graphs. This paper investigates the path privacy disclosure problem in weighted graph, proposes weighted graph k-possible path anonymity (KPPA) to protect against shortest-path-based attacks on shortest path identification, and develops a weight generalization based approach to achieve KPPA algorithm. Extensive experiments on real data sets show that the algorithm performs well. Meanwhile, it can retain the structural properties of the original graph and increase the utility of the weight information.

Key words:  weighted social networks, path privacy, weight generalization, shortest path

摘要: 随着社会网络的普及,社会网络数据的隐私保护问题,已经成为数据隐私研究领域学者普遍关注的热点问题。由于隐私信息异常广泛,攻击者可以利用多种背景知识进行隐私攻击。现有的隐私保护技术,大多针对简单社会网络,并不适用于加权社会网络。对加权社会网络中的路径隐私泄露问题进行了研究,针对最短路径识别提出了加权图k-可能路径匿名(k-possible path anonymity,KPPA)隐私保护模型,来防止基于加权社会网络的最短路径隐私攻击,设计了一种基于权重泛化的匿名方法来实现KPPA算法。通过在真实数据集上的大量测试研究,证明了KPPA算法对于加权图路径隐私保护的有效性,同时基于KPPA算法可以保留原图结构性质,提高权重信息的可用性。

关键词: 加权社会网络, 路径隐私, 权重泛化, 最短路径