社交网络匿名与隐私保护
息、医疗信息等大规模数据被无节制地搜集、分析与交易利用，那么用户都将“被透明”，不仅个人隐私荡然无存，还将引发一系列社会问题。因此，如何深入理解社交网络的匿名化与去匿名化这一对互相依存的博弈过程，更好地在社交网络活动中保护用户个人隐私，成为当前大众的关注焦点。
社交网络服务匿名与隐私保护目标
在社交网络模型中，需要匿名及隐私保护的主要对象包括：
1.身份隐私：指社交网络中的虚拟节点所对应的真实身份信息。通常情况下，互联网服务提供商对外提供匿名化处理后的社交网络信息，如各种社交关系或属性信息特征等。但是分析者一旦将虚拟节点和真实的用户身份相关联，就会造成用户身份信息泄露（也称为“去匿名化”）。用户身份隐私保护的目标是降低攻击者从虚拟节点中识别出某特定用户的可能性。
2.社交关系隐私：社交关系数据本身蕴含了巨大价值。互联网服务提供商可基于用户现有的社交结构分析用户的交友倾向、向用户推荐朋友等，有助于保持社交体的活跃和粘性。但与此同时，分析者也可以挖掘出用户不愿公开的社交关系、交友体特征等，从而导致用户的社交关系隐私暴露。为此，社交关系隐私保护要求节点对应的社交关系保持匿名，使攻击者无法确认特定用户拥有哪些社交关系。
3.属性隐私：属性数据在社交网络中变化最频繁，内容最丰富，生动地描述了用户的个性化特征，能够帮助系统建立完整的用户轮廓，提高推荐系统的准确性。然而，用户往往不希望将所有属性信息都对外公开。例如，用户观看私密视频的记录被曝光，会对用户的网络形象造成最直接的破坏，甚至影响用户的正常生活。属性隐私保护要求对社
引言
互联网刚兴起时，美国杂志《纽约客》(The New Yorker)曾刊登了一幅著名漫画，标题为“在互联网上，没人知道你是一条狗(On the Internet, nobody knows you’re a dog)”。从那时起，由于网络的虚拟性和匿名性，每个人都可以选择成为“双面人”。而随着社交媒体的兴起，越来越多的用户选择将个性化的信息分享到社交网络服务(social network service, SNS)，用户网络形象比以往更丰富，也更真实。
因为用户的个性化信息与用户隐私密切相关，所以互联网服务提供商一般会对用户数据进行匿名化处理之后再提供共享或对外发布。表面上看，活跃于社交网络上的信息并不泄露个人隐私。但事实上，几乎任何类型的数据都如同用户的指纹一样，能够通过辨识到其拥有者。在当今社会，一旦用户的通话记录、、银行账户、信用卡信付艳艳1　付　浩2　谢　幸3等1中国科学院软件研究所
2中国科学技术大学
3微软研究院
社交网络匿名与隐私保护关键词：数据挖掘　去匿名化　个性化隐私保护
交网络的属性数据进行匿名化处理，阻止攻击者对用户的属性隐私进行窥探。
在社交网络中，用户的上述三类隐私信息之间往往互相关联、互相影响，增大了隐私保护的难度。用户的身份隐私泄露会立即导致当前节点已标记的社交关系和属性信息泄露；同时，虚拟节点对应的社交关系和属性数据越丰富、越个性化，就越容易被攻击者识别，导致节点身份暴露。现有研究表明，在社交网络中，用户的社交关系和属性具有相关性，可通过用户的社交关系推测其可能具有的属性，反之亦然。
显然，从单一数据特征入手的匿名方案无法满足社交网络隐私保护的需求。一种更为全面的模型为“属性-社交网络模型”[1]。如图1所示，该模型包括用户节
点和属性节点两部分。用户之间具有关联关系的，可形成一条边，称为社交关系。若用户具有某个属性（标签），则在用户和对应的属性间形成一条边，称为属性关系。属性-社交网络模型可以更好地描述如推特、微博的用户数据等各类社交网络数据。基于该模型进行多特征联合匿名，是当前社交网络
隐私保护的重要方向。
社交网络服务匿名
化方法
朴素匿名化方案
为了保护隐私，朴素的匿名
化方法直接删除诸如用户名、姓
名、电话号码等敏感信息，同时
完全保留其他的描述信息和社交
关系结构图（以下简称“图”）的
结构。目前此方法应用最为广泛。
例如，图2中的匿名数据包括学
生的社交关系和成绩等，而学生
的姓名都被替换成了随机数字。
在很多实际应用的场景中，
可以假定攻击者有途径获取少量
真实用户的部分信息（辅助信
息），例如用户对应节点的度数
（朋友数量）、邻居节点间的拓
扑结构（朋友之间的关系）或节
点附近任意范围的子图。攻击者
利用这些辅助信息，在发布的数
据中匹配此类信息以定位目标用
户。例如，若攻击者知道Alice
有至少4个朋友，Bob有3个相
互认识的朋友，则攻击者可以发
现，匿名数据中的4号节点其实
就是Alice，她的成绩是F（Alice
恐怕不想让别人知道这一点）。
基督教与天主教的区别攻击者进一步发现，Bob必然在
节点{2, 3, 6}中，他的成绩在
B+到D+之间，而且可以确定
Bob和Alice一定是朋友。上述
例子说明了匿名数据可能存在的
隐私风险。
巴克斯托姆(Backstrom)等
人[2]指出，攻击者可以在数据发
布之前在社交网站上注册少量账
号，然后在这些账号之间建立特
定模式的连接。在数据发布之后，
攻击者可以仅仅根据图的结构来
快速定位具有此类模式的子图，
从而识别出自己创建的账号，也
可以识别出与之相邻的真实用户
的账号。此外，攻击者即使不事
先创建账号，仍然可以通过收集
少量真实用户间的连接模式来进
行此类攻击。海(Hay)等人[3]发
现，仅通过匹配图中邻居节点的
度数就能唯一确定大多数用户在
图中的位置。上述研究工作表明，
朴素匿名化其实并不能确保隐私2023跨年幽默朋友圈文案
安全。
为了克服朴素匿名化的缺
陷，研究者们提出了一系列针
对不同类型隐私威胁的匿名化算
法。匿名化算法修改图的结构和
描述信息，使其不能与攻击者所
图1　“属性-社交网络”示意图
图2　图的朴素匿名化样例
掌握的辅助信息精确匹配，从而实现隐私保护。通常来讲，对图的改动越大，隐私保护性能越好，但
同时也引入了噪音，降低了数据的可用性。有时为了保证足够的匿名性，可能无法提供高质量的社交网络数据供研究者分析使用，这也是此类匿名化算法很少得到应用的原因之一。根据所采用匿名方法的不同，匿名方案可基本分为两大类：(1)基于结构变换的匿名方案，可采用的手段包括边、节点的抑制、扰动、交换等；
(2)基于超级节点的匿名方案，常用手段为边、节点的泛化。
基于结构变换的匿名方案
基于结构变换的匿名方案是最为典型的社交网络匿名方案。其特点是对社交网络中的边、节点进行增、删、交换等变换来实现匿名。该方案的基本思想是使部分虚拟节点尽可能相似，隐藏各个节点个性化的特征，从而使得攻击者无法唯一地确定其攻击对象。典型的度匿名方案是通过调整度数相似的节点的度数，增加或删除边，增添噪音节点等，使得每个节点至少与其他k-1个节点1的度数相同，使攻击者无法通过节点度数唯一地识别出其攻击目标[4]。在基本方案的基础上，研究者又提出了多种变体，逐步将匿名考量的参数范围扩大，包括相邻节点的度数[5]、邻居结构[6]等。邹磊等人[7]提出了一种匿名化算法，使得匿名化
的图具备自同构性。因为总是能
在目标图中到至少k个不同的
子图与攻击者所掌握的图同构，
所以任何基于图结构的攻击都将
失效。程（Cheng，音译）等人[8]
提出的k同构匿名化算法进一步
确保了边的匿名性：攻击者甚至
不能推测出两个节点之间是否有
边。此类算法可以看作是基于图
结构的“终极”防护。从基本的
度匿名到同构匿名，节点在更多
社交结构特征上更加近似，攻击
者识别出某特定节点的难度也随
之增大，因此可以有效地保护用
户的隐私。但需要指出的是，随
着匿名方案的安全性增强，对图
的改动也越来越大，严重影响数
据的可用性。例如，在应（Ying，
音译）等人的实验中[9]，来自数
据库和计算理论领域的科学家合
作关系图需要添加约70%的边
才能满足自同构性。
也有研究者提出根据社交结
构的其他特征进行结构变换的方
案。例如，应（Ying，音译）等人
提出一种随机增删、交换边的方
案。该方案要求在匿名过程中保
持图的邻接矩阵特征值和对应的
拉普拉斯矩阵第二特征值不变[9]，
从而提高数据的可用性。基于等价
类方案的思想则是根据节点的不
盾山的祝福同特征，将其划分为不同的等价类，
将部分社交连接的顶点用与其相
同等价类的其他顶点代替[10]。此
设置拍一拍好听的后缀
类方案通常是等概率地随机选取
边或节点进行增删、交换。具体
来说，随机删除边的方法是从图
中等概率地选取一定比例的边，
然后删除。随机扰动的方法是先
以相同方式删除掉一定比例的边，
然后再随机添加相同数量的边，
使得匿名化后的图与原图边数相
等。随机交换的方法首先随机选
取两条边(i1, j1)和(i2, j2)，然后删
除之，并添加两条新的边(i1, j2)
和(i2, j1)，前提是这两条边以前并
不存在。随机交换的方法不仅保
证了总边数不变，也保证了每个
节点的度数不变。米塔尔(Mittal)
等人提出了一种基于随机游走的
算法[11]：对于每条边(u,v)，从v
开始进行指定长度的随机游走，
最终到达z。然后将原来的边(u,v)
替换成(u, z)。
基于结构变换的匿名方案的
优势非常明显。首先，此类方案
挑选较为相似的节点进行改造，
能够很好地保持图结构的基本特
征，也易于实现。其次，此类方
案在一定程度上实现了节点的模
糊化，使得节点的部分结构特征
变得不明显，加大了攻击者的识
撒旦是谁别难度，能够保护用户隐私。但
是，此类方案的缺点也十分突出，
仅仅考虑了节点和边的结构特征，
进行边、节点增删、交换的随机
性较大，而并未考虑其实际意义，
可能导致并不相关、甚至差异明
显的节点间建立连接，影响数据
分析结果的一致性。而且，此类
方案添加的噪音过于分散稀少，
1 这里的k是指隐私保护机制“k-匿名”中的参数，用来控制隐私保护的强度。
并不能抵抗针对特定匿名边的分析攻击。攻击者仍可借助一系列去匿名化攻击手段分析出特定的一对节点间是否存在社交连接[5]。
基于超级节点的匿名方案
基于超级节点的匿名方案对图结构进行了分割和聚集操作，匿名后的社交关系结构图与原始社交关系结构图存在较大区别。杰拉瓦(Zheleva)和盖多尔(Getoor)最早提出了这一模型[12]，其后康潘(Campan)和杜鲁塔(Truta)的工作[13]，以及塔萨(Tassa)和科恩(Cohen)的工作[14]进一步完善了此类匿名方案。改进的方案将节点分为多个类，然后将同一类的节点压缩为一个超级节点，两个超级节点之间的边压缩为一条边。在发布的匿名图中，所有超级节点内部的节点和连接都被隐藏，超级节点间
的连接也无法确定连接的真实顶点。研究者还分别根据节点间的距离、节点间属性的差异等特征，实现了不同的超级节点匿名方案。
这类匿名方案基于聚类节点信息的统计发布，能够避免攻击者识别出超级节点内部的真实节点，从而实现用户隐私保护，但很大程度上改变了图数据的结构，使得数据的可用性大为降低。
差分隐私保护方案
微软研究院的辛西娅·德沃柯(Cynthia Dwork)提出差分隐私(differential privacy)的保护方案[15]。差分隐私是一种通用且具
有坚实的数学理论支持的隐私保
护框架，可以在攻击者掌握任意
背景知识的情况下对发布数据提
供隐私保护。该方法关注社交网
络中一个元素的增加或缺失是否
对查询结果产生显著影响，通过
向查询或者查询结果插入噪声来
进行干扰，从而实现隐私保护。
作为一种新型的隐私保护技术，
差分隐私保护在理论研究和实际
应用等方面都具有重要的价值。
它通过对原始数据变换后的内容
或者统计分析结果数据添加噪声
达到隐私保护效果。在数据集中
插入或者删除数据不会影响任何
查询（如计数查询）的结果。近
年来研究人员设计了一系列差分
隐私算法。由于图的节点度数分
布是分析图的一项重要统计量，
海等人提出了一种满足差分隐私
的算法用来计算和发布节点度数
分布[16]。萨拉(Sala)等人提出可
以先抽取图中相邻节点度数，然
后对这些度数做适当修改后，重
新构造和发布一个符合度数约束
的图[17]。
但是，上述方案对攻击者的
能力都存在一些特殊假设，或者
强调攻击者对攻击目标的认识，
或者要求攻击者了解节点的度
数、属性个数等特征。而在如脸
谱、推特、微博等节点迅速变化
的社交网络中，用户的社交连接
变化频繁，假定攻击者能精确地
限定攻击目标的度数一般是不合
理的。实际上，攻击者对攻击目
标的了解通常是全面但不深入。
例如，攻击者可能了解攻击目标
具有某特定属性和具有某些社交
关系连接等，但不清楚该目标的
其它属性，也不了解其属性个数。
攻击者会通过各类信息的综合分
析，从海量数据集中过滤出攻击
目标来提高攻击成功的概率。如
果我们假设攻击者仅仅依靠单一
特征锁定攻击目标，实际上是
大大低估了攻击者的信息收集能
力。因此，建立合理的攻击者能
力模型也是当前隐私保护方案需
要解决的问题。
社交网络服务去匿
名化研究
与隐私保护研究相对应，在
实际研究中需要开展去匿名化研
究，即研究如何去除虚拟节点伪
装，根据公开信息推测出用户可
能的敏感信息或倾向等。隐私保
护与去匿名化研究正如盾与矛的
关系。为了更好地保护社交网络
中用户的隐私信息，制定匿名程
度高的隐私保护方案，必须充分
了解攻击者可能的去匿名化手
段，并进行对应的强化匿名处理。
去匿名化通常需要攻击者收
集与目标相关的辅助信息，例如
其附近的子图结构、个人资料等，
利用这些信息反推出被掩盖的敏
创业板怎么开通感信息。根据攻击者获取的辅助
信息的来源和精确程度的不同，
去匿名化研究可分为基于特定模
式精确匹配的去匿名、基于种子
匹配的去匿名和基于相似度匹配
的去匿名三类。
巴克斯托姆等人[2]以及海等人[3]提出的去匿名化方法主要是基于对特定模式的精确匹配，数据一旦经上述某种匿名化算法引入噪声，就不再有效了。
同一个人在不同的社交网络中的社交关系具有一定的相关性。基于这一现象，纳拉亚南(Narayanan)和沙玛提科夫(Shmatikov)[18]设计了一种匹配两个不同网络间相同用户的去匿名化算法。攻击者首先需要了解一定数量的用户在两个图之间的节点对应关系（种子匹配）。如果已知节点u的邻居节点对应于另一个图的一些节点，那么后者的公共邻居v则很有可能也对应于u。基于此思路，算法从种子匹配出发，沿着边传播节点与节点之间的相似度分值。如果两个节点都和对方最相似，并且这种相似足够显著，那么就将他们匹配起来。由于算法执行的前期可能会因为信息不足造成错误的匹配，因此算法还会反向传播相似度以修正这些错误。研究者使用此算法成功匹配了约1/3同时使用推特和Flickr的用户。纳拉亚南等人后来还利用去匿名化算法赢得了IJCNN 2011社交网络挑战的冠军。
攻击者能够获取的辅助信息可能充满噪声。例如，社交网络总是在不断演化，如果匿名数据是在很长
时间以前发布的，根据当前的社交网络难以推断当时的情况。另外，被发布的数据往往只是完整社交网络一个很小的子集，要在其中锁定一个足够小的
范围有较大难度。此外，考虑到
数据的可用性，实用的匿名化方
法不可能对图作过多修改。因此，
一些对数据改动较小的匿名化算
法（包括朴素匿名化算法）仍有
一定市场。尽管纳拉亚南和沙玛
提科夫提出的算法可以应用于此
类情况，但匿名化的成功与否严
重依赖种子匹配的数量和质量。
在实际攻击中，种子匹配的准确
率其实很难保证。在攻击者没有
种子匹配的假设下，我们提出了
一种基于图结构和属性的节点相
似度，并将其应用于去匿名化[19]。
两个节点相似与否取决于它们
的邻居节点是否相似。邻居节
点的相似是从一一映射的角度
来衡量的。
具体而言，设i和j是分别
来自两个图的节点，S(i, j)是它
们的相似度，那么S(i, j)递归定
义如下：
其中N1(i)表示节点i的邻居节
点，θ是节点i和j的邻居之间
的一一映射。
相似度的定义可以进一步扩
展，以利用节点和边上的属性信
息。最后，按照总体相似度最大
化的原则，两个图节点间的一一
映射被作为匿名化的结果。算法
的流程如图3所示。利用这一算
法，我们赢得了WSDM 2013数
据挑战中去匿名化项目的冠军。
除此之外，还有一部分研究
工作关注诸如用户资料、关系的
类型强度等属性信息的保护。梅
丝洛夫(Mislove)等人[20]通过
研
图3　基于节点相似度的去匿名化示例

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。