郭彩华　王　斌　朱怀杰　杨晓春

(东北大学信息科学与工程学院　沈阳　110004)(zhuhjneu@gmail.com)



增量的动态社会网络匿名化技术

郭彩华王斌朱怀杰杨晓春

(东北大学信息科学与工程学院沈阳110004)(zhuhjneu@gmail.com)

摘要随着社会网络的快速发展和普及，如何保护社会网络中的敏感信息已成为当前数据隐私保护研究领域的热点问题.对此，近年来出现了多种社会网络匿名化技术. 现有的匿名技术大多把社会网络抽象成简单图，然而实际生活中存在大量增量变化的社会网络，例如email通信网络，简单图并不能很好地刻画这种增量变化，因此，将社会网络抽象成增量序列具有现实意义.同时，在实际生活中大部分网络是带有权重信息的，即很多社会网络以加权图的形式出现，加权图与简单图相比携带了更多社会网络中的信息，也会带来更多的隐私泄露. 将增量的动态社会网络抽象成一个加权图的增量序列. 为了匿名加权图增量序列，提出了加权图增量序列k-匿名隐私保护模型，并设计了基于权重链表的baseline匿名算法WLKA和基于超图的匿名算法HVKA来防止基于结点标签和权重链表的攻击. 最后，通过在真实数据集上的大量测试，证明了WLKA算法能够保证加权图增量序列隐私保护的有效性，HVKA算法则在WLKA的基础上更好地保留了原图的结构性质并提高了权重信息的可用性，同时还降低了匿名过程的时间代价.

关键词动态社会网络；增量序列；数据隐私；权重链表；超图；信息损失

随着互联网的发展，出现了越来越多的网络平台，用户在网络上共享信息并参加各种各样的活动.社会网络的出现给人们的生活带来了极大的便利，但随之而来的是越来越多的社会网络数据被发布到网络上，导致隐私泄露.近年来，如何在发布网络数据的同时保护敏感信息成为了研究热点.目前大部分社会网络隐私保护技术主要针对简单图，然而实际生活中存在大量增量变化的社会网络，例如email通信网络，简单图并不能很好地刻画这种增量变化，因此，将社会网络抽象成增量序列具有现实意义.

文献[1]考虑了社会网络的动态性，将社会网络抽象成一系列图组成的增量序列，即下一时刻图中结点和边都是增加的，并针对简单图增量序列的隐私问题进行了研究.该文把简单图增量序列定义为g=〈G0,G1,…,GT〉，时刻t的社会网络图表示为Gt=(Vt,Et,Lt)，其中Vt代表时刻t结点的集合，Et代表时刻t边的集合，Lt代表时刻t结点标签的集合.由于它是一个增量序列，因此，Vt-1⊆Vt，Et-1⊆Et，Lt-1⊆Lt.

文献[1]中的匿名方法保证Gt(t=0,1,…,T)符合k匿名，即攻击者以结点标签为背景知识识别任意结点的概率不大于1k.它不仅考虑了攻击者将结点标签作为背景知识，同时也将社会网络的动态变化视为背景知识.图1(a)(b)分别是简单图增量序列g=〈G0,G1〉在时刻t为0或1的原始图，时刻t=1新增加的结点和边用虚线标出.在文献[1]的匿名算法中通过将标签相近的结点分为一组，使得同组结点基于标签不可区分，k=2时，时刻t为0或1的分组结果分别如图2(a)(b)所示，匿名图分别如图1(c)(d)所示.每个标签均对应2个结点，所以攻击者以结点标签为背景知识准确识别任意1个结点的概率均不大于50%.例如，攻击者知道Alice的标签是{25,M,TW}，首先单独针对图2(a)(或图2(b))所示的分组结果中均有2个结点v5,v8与标签{25,M,TW}对应，所以攻击者识别Alice的概率为50%.另外，再联合不同时刻t为0或1的分组结果同样不能正确识别结点身份，所以攻击者仍然无法正确识别Alice.

然而，在现实中进行社会网络分析时，发现结点之间的边是带有权重信息的，即存在许多加权社会网络图.例如在金融交易网络中，边权重表示企业之间交易金额的大小.在文献合作关系网中，边权重表示作者之间合作的次数.在email通信网络中，边权重表示实体之间发送邮件的次数.在朋友关系网中，边权重表示朋友之间关系的密切程度.跟简单图相比，加权图携带了更多社会网络中的信息，更能准确地表示现实世界中的社会网络，具有更强的描述能力，同时也会带来更多的隐私泄露，因此对于加权社会网络的隐私保护更为重要.文献[1]中并没有考虑权重信息对结点隐私的影响.图1(f)是G1的加权图，假设攻击者知道结点Alice的标签{25,M,TW}及权重链表〈3,1〉(权重链表是指结点与邻居连接边上的权值按降序排列得到的权重序列).攻击者根据标签得到2个候选结点v5,v8，再根据权重链表则可得到唯一的候选结点v8，正确识别结点的概率为100%，这就导致了用户身份信息泄露.

现有的动态社会网络隐私保护模型只考虑了简单的无权图，并没有考虑加权图.对此，本文将社会网络抽象成加权图增量序列，并对加权图增量序列上的隐私问题进行研究.本文是第1篇解决加权图增量序列隐私保护问题的文章.本文的方法包括3部分：

1) 对加权图增量序列最后一时刻的原始图中所有结点分组，分组方法采用文献[1]中对结点分组的方法，使得同一分组中的结点基于标签不可区分；

2) 对每个分组中所有结点的权重链表匿名，使得同一分组中所有结点基于权重链表不可区分；

3) 根据时刻t(t=0,1,…,T)的匿名图推出时刻t-1的匿名图，重复这个过程直到所有时刻的图都完成匿名.

Fig. 1　An example of anonymity incremental sequence g=〈G0,G1〉(k=2).图1　增量序列g=〈G0,G1〉的匿名化实例(k=2)

v1,v2v3,v4v5,v8v6,v9v7,v1025,F,TW22,M,TW24,M,TW24,M,TW18,M,US25,M,TW35,M,US33,F,US28,F,JP30,F,JPv1,v2v3,v4v5,v8v6,v925,F,TW22,M,TW24,M,TW24,M,TW18,M,US25,M,TW35,M,US33,F,US(a)Groupingresults(t=0)(b)Groupingresults(t=1)

Fig. 2Grouping results of g=〈G0,G1〉(k=2).
图2增量序列g=〈G0,G1〉的分组结果(k=2)

本文的主要贡献如下：

1) 引入了增量序列分类安全条件(ISCSC)来指导匿名过程，并在此基础上提出了加权图增量序列k-匿名隐私保护模型，从而有效地防止攻击者以标签及权重链表为背景知识的隐私攻击；

2) 设计了一个基于权重链表的baseline匿名算法WLKA，WLKA算法能够保证加权图增量序列隐私保护的有效性；

3) 设计了基于超图的HVKA隐私保护算法，在生成匿名图的同时，能够提高图数据的可用性并减少匿名的时间代价；

4) 通过在真实数据集上的大量实验测试和分析，验证了加权图增量序列k-匿名隐私保护模型的有效性以及发布图数据的高可用性.

1相关工作

随着互联网技术的迅速发展，社会网络应用不断涌现，管理和分析社会网络数据成了研究热点.然而在社会网络数据中隐藏着大量的敏感信息，发布和共享社会网络数据会导致隐私泄露，由此，近年来越来越多的研究学者开始把注意力集中到社会网络数据的隐私保护问题上，并提出了多种匿名方法.

文献[2]提出了k-度匿名，用来防止攻击者基于结点度的隐私攻击，该方法使得匿名图中对任意1个结点，至少存在k-1个其他结点与其度相同.文献[3]设计了k-邻居匿名方法，用来防止基于1-邻居图的隐私攻击，该方法使得匿名图中对任意一个结点的1-邻居图，至少存在k-1个结点的1-邻居图与其同构.文献[4]提出了k-自同构，是指图自身存在着k个同构映射，使得攻击者进行结点身份识别时，至少存在k个候选符合.文献[5]提出了k-同构模型，把社会网络分为k个子图，使子图之间互相同构，从而防止隐私泄露.

文献[6-10]把结点与邻居连接边上的属性值序列作为背景知识.文献[6]中把结点与邻居连接边上的属性值序列定义为权重包，并提出k-直方匿名，使得对任意一个结点，至少存在k-1个其他结点与其权重包相同；文献[7]提出的加权图匿名化方法是使得对于任意结点的权重包，至少存在k-1个其他结点的权重包与其距离小于阈值，而不是相等；文献[8]提出了k-可能隐私保护模型，并通过边权重概括将加权图匿名化为k-可能图；文献[9]讨论了社会网络上的隐私问题，并允许用户设定个性化隐私；文献[10]针对加权社会网络中最短路径识别提出了加权图k-可能路径匿名隐私保护模型来防止基于最短路径隐私攻击；文献[11]针对障碍空间中保持位置隐私的最近邻查询问题提出了一种第三方可靠服务器的方法，该方法能够保证用户在享受基于位置服务所提供的实际准确答案的同时保证位置信息不被泄露.

文献[12]针对攻击者基于结点属性值进行边再识别隐私攻击，提出了基于聚类的模型.文献[1]中用带标签的无向图表示社会网络，并把社会网络的演变抽象成一个增量序列，解决了增量序列上的结点身份再识别问题.但在现实世界中存在大量的加权图，文献[1]忽略了权重对隐私的影响.因此，本文主要研究动态变化的加权社会网络上的结点身份再识别问题.

2背景知识及问题定义

本文主要考虑加权社会网络增量序列的隐私保护问题.下面对文中用到的基本概念进行详细地介绍，为后续工作奠定基础.

定义1. 加权图增量序列.随时间增量变化的加权社会网络表示为gW=〈GW0,GW1,…,GWT〉，时刻t的社会网络GWt=(Vt,Et,Lt,Wt)，其中，Vt代表时刻t的结点集合，Et代表时刻t结点间边的集合，Lt代表时刻t结点标签的集合，Wt代表时刻t权重链表的集合.假设在t(t=0,1,…,T)的下一时刻社会网络中顶点和边的数量非递减，即Vt-1⊆Vt，Et-1⊆Et，Lt-1⊆Lt，那么称gW为加权图增量序列.

图3(a)(b)分别为加权图增量序列gW=〈GW0,GW1〉在时刻t=0和t=1的快照，时刻t=1增加的结点和边用虚线给出.

Fig. 3　Weighted graph increment sequence gW=〈GW0,GW1〉.图3　加权图增量序列gW=〈GW0, GW1〉

定义2. 结点权重链表.∀v∈V，把v邻边上的权重值降序排列，就得到v的权重链表，记为w=〈w1,w2,…,wd〉，(w1≥w2≥…≥wd)，其中d是结点v的度.

定义3. 权重链表统一化.对图G(V,E,L,W)中所有结点进行分组得到分组集合C，每个分组中至少包含k个结点，∀c∈C，保证c中所有结点的权重链表相同，则称这个过程为权重链表统一化.

对图3(b)所示的加权图进行分组得到的结果如图2(b)所示，结点v3，v4被分为一组，权重链表分别为w3=〈5,3,2〉，w4=〈3,3,2〉，进行权重链表统一化后w3=w4=〈5,3,2〉.

定义4. 结点身份泄露.给定加权图增量序列gW=〈GW0,GW1,…,GWT〉，如果攻击者以结点标签及权重链表为背景知识能够准确识别出结点v，则结点v存在结点身份泄露.

如图1(f)，攻击者根据结点Alice的标签{25,M,TW}和权重链表〈3,1〉能以100%的概率识别出结点v8是Alice，这说明结点v8存在结点身份泄露问题.

问题定义. 加权图增量序列匿名化问题.

1) 对匿名图中任意一条边e，攻击者正确识别其端结点的概率不大于1k.

2) 对匿名图中任意2个结点，攻击者正确判断该结点间存在连接的概率不大于1k.

3) 在匿名图中，攻击者以结点标签及权重链表为背景知识准确识别某结点的概率不大于1k.

3加权图增量序列k-匿名隐私保护模型

为了防止加权图增量序列中结点身份泄露问题，本文提出了基于增量序列分类安全条件的k-匿名隐私保护模型.为了得到满足隐私目标的k-匿名隐私保护模型，先给出一些例子和性质.

例1. 如图3(b)中假设v1和v3被分为1组，攻击者可以确定出v1和v3之间存在连接，违反了隐私目标.另外，对如图4所示的图分组，得到的分组结果为C={{v1,v2},{v3,v4}}，2个分组间存在4条边，攻击者可以确定v1和v2具有相同的朋友v3和v4，从而造成共同朋友关系泄露.

Fig. 4　An example of dense links (k=2).图4　分组间存在大量边的例子(k=2)

根据例1的分析，我们可以得到性质1.

性质1. 对于gW中任意时刻原始图的匿名，同一分组及2个分组间均不能存在大量的边，否则会造成隐私泄露.

例2. 如图3为加权图增量序列gW=〈GW0,GW1〉，首先对GW1进行匿名，假设得到的分组结果为C={{v1,v2},{v3,v4},{v5,v8},{v6,v7},{v9,v10}}.接下来，通过移除时刻t=1添加的结点和边得到时刻t=0的匿名图，分组结果变为C={{v1,v2},{v3,v4},{v5,v8},{v6}, {v9}}，分组{v6}和{v9}不符合k=2的匿名约束条件，造成隐私泄露. 这样可以分析得到，时刻t-1的匿名图是通过移除时刻t(t=1,2,…,T)添加的结点和边得到的，由于在移除结点后，包含移除结点的分组的大小有可能小于k，所以结点的移除将会造成隐私泄露.

根据例2的分析，我们可以得到性质2.

性质2. 对于gW中任意时刻原始图的匿名，同一分组中的结点必须来自同一时间戳，否则会造成隐私泄露.

为了防止上述性质1和性质2中情况的发生，本文引入文献[1]中指导结点分组过程的时间序列分类安全条件，定义加权图增量序列匿名的增量序列分类安全条件(incremental sequence class safety condition， ISCSC)，对结点分组的过程中，必须满足ISCSC.

定义5. 增量序列分类安全条件(ISCSC).对结点集Vt的分组满足ISCSC，当且仅当∀v∈Vt及∀C⊂Vt满足如下条件：

1) ∀v∈Vt′，∀w∈Vt′：v∈C∧w∈C⟹t=t′.

2) ∀(v,w)∈Et：v∈C∧w∈C⟹v=w.

3) ∀Ca,Cb⊂Vt，ne是Ca和Cb之间边的个数⟹ne≤k.

条件1表明了同一分组中的结点来自同一时间戳；条件2限制了对任一时间戳同一分组中不含边；条件3限制了对任一时间戳2个分组之间边的数量.

定理1. 对加权图增量序列gW=〈GW0,GW1,…,GWT〉的匿名过程中，满足增量序列分类安全条件(ISCSC)是实现隐私目标的充分条件.

证明. ISCSC的条件1(∀v∈Vt′，∀w∈Vt′：v∈C∧w∈C⟹t=t′)保证了在∀时刻t(t=0,1,…,T)的匿名图中同一类中的结点属于同一时间戳，也就是说，在时刻t-1(t=1,2,…,T)删除的结点都属于同一个类，因此删除后剩余的每个类中仍包含k个结点.攻击者不能根据多重发布识别用户的身份信息.

ISCSC的条件2(∀(v,w)∈Et：v∈C∧w∈C⟹v=w)限制了对任一时间戳同一类中不含边.如果在时刻t(t=0,1,…,T)的匿名图中2个结点间存在一个边，那么这2个结点的真实标签必然属于不同的类.此外，匿名后每个类有k个标签并且各个类的标签不重叠.因此，对于任意一条边，它的2个端点都存在k个候选标签，保证了隐私目标1.

ISCSC的条件3(∀Ca,Cb⊂Vt，ne是Ca和Cb之间边的个数⟹ne≤k)限制了对任一时间戳2个类之间边的数量小于或等于k.假设时刻t存在2个类class1和class2，并且用户user1属于class1，user2属于class2，那么用户user1和user2之间存在边的概率可表示为

P(edge(user1,user2))=

因为class1和class2的大小是k，并且概率P(edge(user1,user2))应该小于或等于1k，因此可推导出ne≤k.所以2个类之间边的数量小于或等于k保证了隐私目标2.

综合以上3点可知，要想实现隐私目标就必须在分组的过程中满足ISCSC，所以满足ISCSC是实现隐私目标的充分条件.

证毕.

定义6. 加权图增量序列k-匿名隐私保护模型.给定加权图增量序列gW=〈GW0,GW1,…,GWT〉，参数k.

1) 将图GWT中所有结点分成大小至少为k的若干分组，分组过程满足ISCSC；

为了提高匿名图的可用性，将属性相近的结点分到同一组或者相邻组中，对此我们定义属性优先列表，在分组前根据属性优先列表将结点进行排序.排序的顺序和ISCSC共同决定了结点的分组.

定义7. 属性优先列表.给定一个属性列表a0,a1,…,an，按属性对查询的重要程度降序排列，得到属性优先列表，记为listap={a0,a1,…,an}，对于任意i

listap=〈location,gender,age〉.

4加权图增量序列的隐私保护算法

为了获得符合加权图增量序列k-匿名隐私保护模型的匿名序列，本节首先给出一种基于权重链表的baseline算法WLKA.随后，为了提高匿名图的可用性，给出一种基于超图的高效匿名算法HVKA.

4.1基于权重链表的baseline算法

在研究动机中分析到如果直接采用文献[1]的方法，也可能会造成隐私泄露问题.本文首先借鉴文献[1]中对结点分组的方法给出了满足ISCSC的分组算法Grouping，然后在分组算法的基础上给出基于权重链表的baseline算法WLKA.

算法1. 分组算法(Grouping).

输入：原始图GWT、参数k、属性优先列表listap;

输出：分组集合C.

① 初始化：有序表Vlist=∅，分组集合C=∅；

② 根据listap排序GWT中结点，返回有序表Vlist；

③ 创建只包含Vlist中第1个结点的分组c,C=C∪{c}；

④ FOR ∀v∈Vlist

⑤ FOR ∀c∈C

⑥ IFSize(c)

⑦c=c∪{v}, break;

⑧ END IF

⑨ END FOR

⑩ IF没找到小于k的分组或者不满足ISCSC THEN

c=c∪{v}；

根据文献[1]以及加权图增量序列k-匿名隐私保护模型，可以得到性质3.

性质3. 分组算法Grouping利用属性优先列表以及ISCSC指导分组得到集合C；再对C中每个分组进行权重链表统一化.由此得到匿名图是安全的.

结合性质3和定义5，本文提出了基于权重链表的k-匿名算法(WLKA)，如算法2所示.

算法2. 基于权重链表的k-匿名算法(WLKA).

输入：加权图增量序列gW=〈GW0,GW1,…,GWT〉；

① 基于Grouping算法生成GWT的分组集合C；

② FOR ∀c∈C

③ 对c中每个结点进行权重链表统一化；

④ END FOR

⑥ WHILEt!=0

⑦ 移除v∈VtVt-1及与其相连的虚拟结点，e∈EtEt-1；

⑧ 再次对每个分组c中的结点进行权重链表统一化；

⑩t=t-1；

以图3(a)(b)所示的加权图增量序列gW=〈GW0,GW1〉为例描述WLKA的匿名过程，匿名结果如图5所示.由于对GW1进行权重链表统一化过程中v6和v9的权重链表维数不同，因此在v9上添加了虚拟结点v11，同理也在v10上添加了虚拟结点v12.

Fig. 5　Anonymous results of WLKA on g=〈GW0,GW1〉.图5　gW=〈GW0,GW1〉的WLKA匿名结果

4.2基于超图的k-匿名算法

算法2为加权图增量序列提供了一种有效的匿名算法.WLKA算法为了实现权重链表统一化，会添加虚拟结点，并改变边权重，这将导致可用性下降，而且WLKA算法需要对每一时刻单独进行权重链表统一化，带来了较大的时间代价.为了提高匿名序列的可用性和减少时间代价，本节提出一种基于超图的k-匿名算法HVKA.

给出基于超图的k-匿名算法HVKA之前，先给出超图的基本定义以及超图可用性的性质.

定义8. 超图、超边、超点.超图是指将原图中所有结点和边聚合成若干超点和超边后构成的图.其中超点hvi代表图中的一组结点,超边ehvi,hvj代表超点hvi和hvj间所有可能的边.

例如，对图3(b)所示的GW1中所有结点聚合得到图6(a)所示的超图，结点v1,v2聚类成超点hv1，结点v3,v4聚类成超点hv2，超边ehv1,hv2代表了hv1和hv2间所有的边ev1,v3，ev2,v4.

Fig. 6　Anonymous results of HVKA on g=〈GW0,GW1〉.图6　gW=〈GW0,GW1〉的HVKA匿名结果

下面给出计算超边的权重定义.

超边的权重定义为原始图边权重的平均值：

(1)

其中，IJ=E∩(hvi×hvj).

例如，由图3(b)所示的GW1经聚合得到图6(a)所示的超图，结点v1,v2聚类成超点hv1，结点v3,v4聚类成超点hv2.根据等式(1)可算得hv1和hv2间的权重为

w′(hv1,hv2)=[w(v1,v3)+w(v2,v4)]2=3.0.

同理可得：

w′(hv1,hv3)=1.5,

w′(hv1,hv5)=2.5,

w′(hv2,hv3)=4.0,

w′(hv2,hv4)=2.0，

w′(hv2,hv5)=2.0.

算法3给出了聚合算法Aggregating的伪代码.聚合算法Aggregating的作用是将分组集合C中同一分组中的结点聚类成超点，不同分组间的边聚类成超边，同时计算超边上的权重，从而得到超图，也就是匿名图.

算法3. 聚合算法(Aggregating).

输入：原始图GWT及分组集合C；

① FOR ∀ci∈C

②hvi={vi}；*建立包含ci中一个结点的超点*

③ FOR ∀vj∈ci

④hvj={vj}；*建立包含ci中另一个结点的超点*

⑤hvnew=hvi∪hvj；*将2个超点合并*

⑥ui=hvi的邻结点；*记录2个超点的邻结点*

⑦uj=hvj的邻结点；

⑧ FOR ∀u∈ui∪uj

⑨ 建立超边eu,hvnew；*建超点与邻结点间超边*

算法4. 基于超图的k-匿名算法(HVKA).

输入：加权图增量序列gW=〈GW0,GW1,…,GWT〉；

① 基于Grouping算法生成GWT的分组集合C；

④ WHILEt!=0

⑦t=t-1；

⑧ END WHILE

定理2. 在匿名过程中，边权重改变量越小，匿名图就能更好地保留原图的性质，可用性就越高.

HVKA算法借助超图的思想在匿名过程中对权重的改变量较小，并且不需要添加大量虚拟结点.根据定理2可知，经HVKA匿名得到的匿名图具有高可用性.

(2)

其中，w′(i,j)为匿名后的权重，W(GWT)为原始图GWT中所有边权重取值之和.

5性能分析与评价

本节对WLKA和HVKA隐私保护算法进行性能分析和评价，采用真实社会网络数据集Cond-Mat-200*http://www.cise.ufl.edu/research/sparse/matrices/Newman/cond-mat-2005和Astro-Ph*https://snap.stanford.edu/data/ca-AstroPh.html进行实验分析和测试，数据集的描述如表1和表2所示.

数据集Cond-Mat-2005为科研人员在凝聚态物理研究领域合作发表论文的加权网络，分别获取该网络在1995-12-03,1998-03-03,2001-04-03,2005-05-18的图数据，作为加权图增量序列的时刻t=0,1,2,3的社会网络图.表1展示了每一时刻增加的结点和边的数目，总共包含了40 421个结点和175 692条边.每条边的权重表示科研人员之间合作发表论文的数目[13]，Cond-Mat-2005的平均边权重值为0.28.

Astro-Ph描述了天体物理学研究领域中科研人员之间的合作发表论文的加权网络，表2所示的时刻t=0,1的社会网络图是该网络在1998-11-06和1999-02-01的图数据，总共包含了16 706个结点和121 251条边.Astro-Ph的平均边权重值为0.51.

Table 1　Cond-Mat-2005 Datasets Description

Table 2　Astro-Ph Datasets Description

由于数据集Cond-Mat-2005和Astro-Ph都不含标签，所以本文中人工生成了标签和权重，所有值满足统一分布.其中标签含有3个属性：年龄(10～60)、性别(男或女)以及位置(50个国家).实验测试的软硬件环境如下：1)硬件环境. Intel Core 2 Quad 2.66 GHz CPU，4 GB DRAM内存.2)操作系统平台.Microsoft Windows 7.3)编程环境. Java，Eclipse.

5.1执行时间

图7显示了在不同数据集上，WLKA和HVKA算法的执行时间随k值大小的变化情况. 从实验结果可以看出，HVKA算法的执行时间小于WLKA算法，这是因为WLKA算法要单独为每一时刻进行权重链表统一化，而HVKA算法则只需在时刻t=T对结点和边进行处理，这就大大减少了匿名边权重造成的时间代价.随着k值的增大，WLKA和HVKA算法的执行时间均逐渐减少，这是由于k越大分组数量越少，验证是否符合ISCSC的次数也越少. 但HVKA算法的执行时间始终小于WLKA算法的执行时间.

Fig. 7　Running time for different k values.图7　执行时间随k值的变化

首先考虑匿名权重对图数据可用性的影响，即发布的匿名加权图增量序列中边权重信息的保持程度.

图8分别显示了在2个数据集上不同时刻边权重取值的分布情况.对于HVKA算法生成的匿名序列中与结点相连的边及边权重都是不确定的，对此采用抽样一致图方法随机抽取与匿名图一致的图，然后在此抽样图上进行分析.主要的做法是为每个结点分配候选边及边权重得到抽样图，然后统计抽样图的权重分布，重复这个步骤得到多个抽样图的权重分布，最后取这些权重分布的平均值作为最终结果.当k=20时，在图8(a)～(f)中，经过HVKA算法生成的匿名图和原始图的权重分布十分接近，WLKA算法生成的匿名图与原始图有较大的偏差.当k=50时，在图8(g)(h)中，经过HVKA算法生成的匿名图和原始图的权重分布仍然非常接近，而WLKA算法生成的匿名图与原始图有了更大的偏差.

本文利用单跳查询来评估匿名加权图增量序列的可用性.单跳查询涉及同一周期中一对不同属性的结点，形式化描述为：在一个时间周期具有某一属性的结点和另一属性结点间存在多少连接. 例如，

Fig. 8Distribution of edge weight and frequency.
图8边权重与频率分布情况

在一个测量周期，美国的用户和日本的用户间存在多少朋友关系.本文通过计算查询结果的平均相对误差来度量匿名方法的可用性.定义相对误差为

其中，q是在原始图上的查询结果，q′是匿名图上的查询结果.由于匿名图中结点标签是不确定的，所以无法在匿名图中执行查询操作，对此同样使用抽样一致图方法随机抽取与匿名图一致的图，然后在此抽样图上进行查询.

图9展示了在不同的属性优先队列下，对WLKA算法在2个数据集上得到的匿名序列进行单跳查询所得结果的相对误差随k值的变化情况.从图9的4幅图中均可看出，k越大，每一时刻单跳查询的相对误差就越大，这是由于随着k的增加，结点的候选标签数随之增加，从而造成了查询结果的相对误差越来越大.图9(a)为没有考虑属性优先队列的情况，所有时间戳的平均相对误差都超过3.2%.图9(b)则为匿名前按属性优先队列listap=〈location,gender,age〉(LGA)对结点进行排序的情况，平均相对误差降到0.4%以下，这是因为排序后同一分组中结点具有相似的属性，从而导致单跳查询的相对误差变小.属性优先队列对数据集Astro-Ph的影响如图9(c)(d)所示，再次验证了属性优先队列对减小查询结果相对误差的重要性.

图10为对2个数据集的HVKA匿名序列进行单跳查询所得结果的相对误差随k值的变化情况.对比图9(b)和图10(a)、图9(d)和图10(b)可以看出，HVKA匿名序列单跳查询的相对误差要比WLKA匿名序列单跳查询的相对误差小.这是由于单跳查询只考虑不同属性结点间的关联，HVKA算法的匿名过程中添加的虚拟结点不包含边，所以添加虚拟结点并没有改变匿名序列中边的总数，因此对单跳查询结果的影响并不大；而WLKA算法的匿名过程中为了实现权重链表统一化会添加虚拟边，导致单跳查询结果的相对误差增大.

Fig. 9　The relative error of single hop query on WLKA anonymous sequences.图9　WLKA匿名序列单跳查询的相对误差

Fig. 10　The relative error of single hop query on HVKA anonymous sequences.图10　HVKA匿名序列单跳查询的相对误差

6结束语

本文研究了加权图增量序列的隐私保护问题.为了匿名加权图增量序列，本文提出了加权图增量序列k-匿名隐私保护模型，并在此基础上设计了基于权重链表的baseline算法WLKA和基于超图的k-匿名算法HVKA，从而有效地防止结点身份再识别和边权重泄露等隐私攻击.最后基于大量实验测试和分析，验证了WLKA算法能够有效地防止结点身份泄露和边权重泄露；HVKA算法则在保证了加权图增量序列隐私保护有效性的基础上提高了匿名图的可用性，同时也降低了匿名过程的时间代价.

参考文献

[1]Wang C J L, Wang E T, Chen A L P. Anonymization for Multiple Released Social Network Graphs[M] //Advances in Knowledge Discovery and Data Mining. Berlin: Springer, 2013: 99-110

[2]Liu K, Terzi E. Towards identity anonymization on graphs[C] //Proc of the 2008 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2008: 93-106

[3]Zhou B, Pei J. Preserving privacy in social networks against neighborhood attacks[C] //Proc of the 24th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2008: 506-515

[4]Zou L, Chen L, Özsu M T. K-automorphism: A general framework for privacy preserving network publication[J]. The VLDB Journal, 2009, 2(1): 946-957

[5]Cheng J, Fu A W, Liu J. K-isomorphism: Privacy preserving network publication against structural attacks[C] //Proc of the 2010 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 459-470

[6]Yuan M, Chen L. Node protection in weighted social networks[C] //Proc of Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2011: 123-137

[7]Li Y, Shen H. Anonymizing graphs against weight-based attacks[C] //Proc of the Int Conf on Data Mining Workshops (ICDMW). Piscataway, NJ: IEEE, 2010: 491-498

[8]Liu X, Yang X. A generalization based approach for anonymizing weighted social network graphs[C] //Proc of Int Conf on Web-Age Information Management. Berlin: Springer, 2011: 118-130

[9]Yuan M, Chen L, Yu P S. Personalized privacy protection in social networks[J]. The VLDB Journal, 2010, 4(2): 141-150

[10]Chen Ke, Liu Xiangyu, Wang Bin, et al. Anonymizing weighted social network graph against path-based attacks[J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(11): 961-972 (in Chinese)(陈可, 刘向宇, 王斌, 等. 防止路径攻击的加权社会网络匿名化技术[J]. 计算机科学与探索, 2013, 7(11): 961-972)

[11]Zhu Huaijie, Wang Jiaying, Wang Bin, et al. Location privacy preserving obstructed nearest neighbor queries[J]. Journal of Computer Research and Development, 2014, 51(1): 115-125 (in Chinese)

(朱怀杰, 王佳英, 王斌, 等. 障碍空间中保持位置隐私的最近邻查询方法[J]. 计算机研究与发展, 2014, 51(1): 115-125)

[12]Bhagat S, Cormode G, Krishnamurthy B, et al. Class-based graph anonymization for social network data[J]. The VLDB Journal, 2009, 2(1): 766-777

[13]Newman M E J. The structure of scientific collaboration networks[J]. Journal of the National Academy of Sciences, 2001, 98(2): 404-409

Guo Caihua, born in 1990. Master. Her main research interests include social network privacy protect.

Wang Bin, born in 1972. Associate professor. His main research interests include query processing and optimization, and distributed data management.

Zhu Huaijie, born in 1988. PhD candidate. Student member of China Computer Federation. His main research interests include spatial database and management, location privacy.

Yang Xiaochun, born in 1973. Professor and PhD supervisor. Senior member of China Computer Federation. Her main research interests include database technique and theory, and data quality analysis.

Incremental Dynamic Social Network Anonymity Technology

Guo Caihua, Wang Bin, Zhu Huaijie, and Yang Xiaochun

(CollegeofInformationScienceandEngineering,NortheasternUniversity,Shenyang110004)

AbstractWith the rapid development and popularity of social networks, how to protect privacy in social networks has become a hot topic in the realm of data privacy. However, in most of existing anonymity technologies in recent years, the social network is abstracted into a simple graph. In fact, there are a lot of incremental changes of social networks in real life and a simple graph can not reflect incremental society network well, so abstracting the social network into the incremental sequences becomes more realistic. Meanwhile, in real life most of the network contains weight information, that is, a lot of social networks are weighted graphs. Compared with the simple graph, weighted graphs carry more information of the social network and will leak more privacy. In this paper, incremental dynamic social network is abstracted into a weighted graph incremental sequence. In order to anonymize weighted graph incremental sequence, we propose a weighted graph incremental sequencek-anonymous privacy protection model, and design a baseline anonymity algorithm (called WLKA) based on weight list and HVKA algorithm based on hypergraph, which prevents the attacks from node point labels and weight packages. Finally, through a lot of tests on real data sets, it proves that WLKA can guarantee the validity of the privacy protection on weighted graph incremental sequence. Compared with WLKA, HVKA is better to retain the original structure properties and improves the availability of weight information, but it also reduces the time cost of anonymous process.

Key wordsdynamic social network; incremental sequence; data privacy; weight list; hypergraph; loss of information

收稿日期：2014-07-25；修回日期：2015-08-11

基金项目：国家“九七三”重点基础研究发展计划基金项目(2012CB316201)；国家自然科学基金项目(61173031,61272178)；国家自然科学基金海外及港澳学者合作基金项目(61129002)；高等学校博士学科点专项科研基金项目(20110042110028)；中央高校基本科研业务费专项资金项目(N120504001)

通信作者：王斌(binwang@mail.neu.edu.cn)

中图法分类号TP311

This work was supported by the National Basic Research Program of China (973 Program) (2012CB316201), the National Natural Science Foundation of China (61173031,61272178), the National Natural Science Foundation of China Grant on International Cooperation (61129002), the Research Fund for the Doctoral Program of Higher Education of China (20110042110028), and the Specialized Fund for the Basic Research Operating Expenses Program of Central College (N120504001).