黄茜茜，蒋千越，蒋 琳，熊圳天

(1.哈尔滨工业大学 计算机科学与技术学院，广东 深圳 518000;2.国防科学技术大学 计算机学院，湖南 长沙 410000)

0 引言

社交网络的飞速发展为人们工作生活带来了极大的便利，而其中的个人隐私问题也越来越引发关注和担忧。在社交网络上公开信息是用户的自愿活动，用户通常不知道谁能够访问他们的数据以及他们的数据如何被使用，社交网络中包含很多敏感信息，比如个人信息、朋友关系等，攻击者甚至可能通过个体与个体之间的连接来推断他们的朋友关系以及其他敏感信息。社交网络的隐私保护是以网络节点为对象，利用某种隐私保护模型对其敏感信息进行保护。

对社交网络的研究通常将其抽象为图结构，即形式化为G=(V,E)，图G表示社交网络，每个个体抽象化为一个节点，V表示节点集，节点之间的链接关系用边表示，E代表边集。还可以用三元组表示G=(V,E,W)，其中W表示边上的权值。

常用的隐私保护技术有SWEENEY L提出的k-anonymity[1]、MACHANAVJJHALA A等提出的l-diversity[2]和LI N等提出的t-closeness[3]等，以及在这些模型基础上不断完善的隐私模型。这些基于匿名方法的模型能够在一定程度上保护社交网络的隐私信息，但是对于拥有背景知识的攻击者却无能为力。比如对于匿名发布的社交网络图，攻击者从外部信息得知其中某两个节点来自同一个研究小组，那么攻击者就有很大把握推断他们是朋友关系。

DWORK C提出的差分隐私(Differential Privacy)[4]近年来成为新的研究热点。差分隐私是一种严格的且能被证明的隐私定义，其基本思想是对原始数据或者统计结果添加噪音，使攻击者无法区分某个记录加入或者删除于某个数据集。……