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算法可以保留原图结构性质，提高权重信息的可用性。

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