一种保持节点可达性的图扰动算法

张换香 张晓琳 何晓玉 李海荣

1(内蒙古科技大学工程训练中心 内蒙古 包头 014010)2(内蒙古科技大学信息工程学院 内蒙古 包头 014010)

0 引 言

随着社会网络的发展，用户之间互动和交流产生了大量的数据，社会网络数据隐私信息的安全性成为当今隐私保护研究的热点问题。为了保护社会网络中的隐私信息，研究者提出匿名图化隐私保护技术，通过修改社会网络图，从而使攻击者无法准确获知用户信息，并最大可能地保证匿名图的数据可用性。但是隐私保护过程中并没有考虑匿名技术对可达性的影响，导致可达性查询存在很大的信息损失。

节点间的可达性问题，是指判定图中两节点u、v间是否存在路径，如果存在，则称节点u可达v，记作u→v。节点间的可达性查询在社会网络中有着广泛的应用，例如可以提高用户粘度的好友推荐系统。社会网络分析会泄露用户间的链接关系，对某些用户来说，这种链接关系并不希望被外人知晓。

图1 社会网络图G

研究者提出通链接扰动，即通过删除、添加边来保护链接关系，例如，在图1中，为了保护链接<1,4>，可以从图中删除<1,4>，并将节点1与图中其他节点链接。然而，链接扰动技术并没有考虑节点间的可达性。如图2所示，G1和G2是图1链接扰动后得到的匿名图。尽管G1和G2都隐藏了链接<1,4>，但两者在保护节点可达性的效果上并不相同。具体来说，若将<1,4>中目的节点用节点3替换，则节点1到节点4之间不再可达。但是若将<1,4>中目的节点用节点5替换，则节点1到节点4仍然可达。因此，前者比后者更好地保持了节点间的可达性。

图2 图G的两个匿名图

针对此问题，本文提出一种可达性保持的图扰动RPP(Reachability Preserving Perturbation)算法。该算法利用“统一删除，逐一扰动”策略和添加伪节点的方法，以一定概率扰动社会网络中的边，从而在保持节点可达性的同时很好地保护图的其他结构性质。

1 相关工作

为了保护社会网络中的链接关系，研究者提出通过图扰动技术来保护敏感链接，即通过对社会网络图进行随机修改，使得攻击者不能准确推测出原始图中真实数据。文献[1]提出一种邻居随机的边扰动技术，以一定概率保留边，若需要删除，则用边代替，其中节点w是节点u的r(r≥2)跳邻居节点。文献[2]提出利用安全分组保护交互型社会网络的链接关系，其思想是：将网络抽象成二分图，然后将网络节点分组，并且同一分组内节点在链接关系上不可区分。文献[3]对文献[2]做出扩展用于保护高纬数据。文献[4]针对网络中的公众节点和隐私节点，提出添加伪节点和修改边的链接关系的保护方法。文献[5-6]针对算法执行的复杂度和发布数据的可用性，提出通过添加、删除和交换边保护隐私信息。文献[7]根据两个等价类之间的链接密度，提出了一种计算链接识别概率的方法。在此基础上，应用最小化删除或交换边数目的贪心策略，使链接识别的可能性降低到给定的阈值之下。文献[8]提出了基于子图结构的链接扰乱，即将原始图分割成若干子图，随机的在子图中增加、删除m条边。文献[9]为了保护链接的关联性，首先利用边邻居中心性计算每条边的移除概率p并依据概率p从原始图G中移除w条边，然后在G的补图中选出w条边添加到图G。文献[10]通过引入马尔科夫链并建立传递矩阵P，提出一种基于随机游走机制的图扰动策略，在保护链接隐私的同时降低扰动过程对图数据可用性的影响。文献[11]针对敏感链接关系设计了一个LinkMirage模型，模型中在保护数据可用性的前提下，模糊社会网络图中的社交拓扑结构和提供带有模糊社交关系视图的不受信任的外部应用，从而抵御链接关系再识别攻击。

综上所述，当前基于图扰动思想的隐私保护技术忽视了对节点可达性的保护，导致匿名图在节点可达性(两节点在图中是否存在路径)查询的低可用性。针对此问题，本文提出一种能有效保护节点可达性的图扰动算法，在匿名社会网络的同时降低节点可达信息损失。

2 背景知识及定义

在本文中，社会网络表示成简单有向图G=(V,E)，其中V是节点集，代表社会网络中的用户；E是有向边集，其中是一条有向链接，表示由用户u到v。

定义1(边扰动) 已知社会网络有向图G=(V,E)，节点u，v是节点集V中不同的两个节点。是E中的链接，即∈E，节点w是图中不同于u，v的节点且∉E，边扰动是指做如下操作：

∉E且∈E

即删除边，并添加到有向图，称为扰动边，节点w称为u的假目的节点。

以图G为例，若删除<1,4>并添加<1,5>到图G，则称完成一次边扰动操作，其中节点5称作节点1的假目标节点。

定义2(可达节点) 已知社会网络有向图G=(V,E)，u，v是图中两个不同的节点，若存在路径L，使得节点u沿此路径能够到达节点v，则称节点v是节点u的可达节点，节点对(u,v)称为可达节点对。

以图G为例，节点4与节点7存在路径{<4,5>,<5,7>}，则节点7是节点4的可达节点，节点对(4,7)称为可达节点对。

定义3(r-邻居)r是给定的非负整数，节点对(u,v)是有向图G中的一个可达节点对，dist(u,v)表示可达节点对(u,v)的最短路径长度，若节点v满足条件：

dist(u,v)≤r

则称节点v是节点u的r-邻居，并把所有满足条件的节点集合记作Nr(u)。其中，在社会网络有向图G中，源节点u的所有可达的节点表示为N*(u)；源节点u的1跳邻居节点集合表示为Dst(u)。

以图G为例，并令u=5，则Dst(5)={4,6,7}，N1(5)={5,4,6,7}，N2(5)={5,4,6,7,2}，N3(5)={5,4,6,7,2,1,3}，N4(5)=N3(5)，N*(5)={5,4,6,7,2,1,3}。

定义4(假目标节点集) 已知社会网络有向图G=(V,E)，∈E，假目标节点集PDNS(u,r,s)是指，源节点u的假目的节点w的集合。其中r指源节点u的r-邻居半径(r≥2)，s指PDNS(u,r,s)中包含的节点个数，s≥|Dst(u)|。假设s1=|Nr(u)|-|N1(u)|，s2=|N*(u)|-|N1(u)|。并且s2≥s1≥s，选取PDNS(u,r,s)集合可以分为以下三种情况：

(1)s1≥s，即Nr(u)-N1(u)中节点数目不少于s，则PDNS(u,r,s)={Nr(u)-N1(u)}。

(2)s1

(3)s2

以图G中的节点5为例，并假设r=2、s=2，则PDNS(5,2,2)={2}，由于s1=1

3 保持可达性的图扰动算法

若要隐藏边的存在，只需隐藏源节点u或目的节点v就能够达到目的，因为仅知道源节点u或目的节点v，并不能推测出的存在。本文采用邻居随机扰动策略隐藏边的目的节点，即以某种概率p保留边的目的节点v，并以概率(1-p)用假目的节点w将其替换[1]。社会网络中的边是以概率p保留的，其不可预测性致使文献[1]并不能保持节点的可达性。以图G为例，假定首次处理的是边<1,4>，并且<1,4>的概率为(1-p)，若删除<1,4>并添加<1,5>。此时，节点1和节点4仍然可达，因为此时图中其他边并未扰动；若边<5,4>概率仍是(1-p)，则需要删除<5,4>，导致节点1和节点4不再可达。

为了保持社会网络扰动图的节点可达性，提出一种“统一删除，顺序扰动”UD&OP(Unified Delete&Order Perturbation)策略，所谓的“UD&OP”策略，是指是指首先同时删除概率为(1-p)的边，然后逐一处理这些删除边。算法的思想是：首先，以概率p和(1-p)为社会网络中的边赋值，删除所有概率为(1-p)的边，并将与相应的PDNS(u,r,s)存放入ECN表；其次，顺序扰动ECN表中每条边，直到ECN表为空。表1显示了ECN的数据结构，ECN由两部分构成，其中ECN.edge保存概率为(1-p)的边，而ECN.CN则保存所对应的假目标节点集。

表1 边-候选节点

本算法包括UD和OP两部分，而UD过程中需要将概率为(1-p)的边和相应的假目标节点集存入ECN表中，如何产生假目标节点集是关键问题。对此，提出相应的生成算法PDNSA(Pseudo Destination Node Set)，具体如算法1所示。

算法1Pseudo Destination Node Set

Input: 社会网络图G=(V,E)；源节点u;源节点u的r-邻居半径r,r≥2;PDNS中节点数目。

Output: PDNS(u,r,s)。

1: Dijkstra(G,u)

//计算源节点到图G其他节点的所有最短路径;

2:N1(u)={u}Dst(u);

3: 计算节点u在r范围内所有可达节点，并存入Nr(u);

4: 计算节点u在图G中的所有可达节点，存入N*(u);

5: 计算s1，s2；

6: ifs1>s

7: PDNS(u,r,s)={Nr(u)-N1(u)};

8: else

9: ifs≤s2

10: PDNS(u,r,s)={Nr(u)-N1(u)}∪RandomSelect {N*(u)-Nr(u),s-s1};

11: elses2

12: PDNS(u,r,s)={N*(u)-N1(u)}∪RandomSelect {V-N*(u),s-s2};

13: return PDNS(u,r,s);

PDNSA算法基于单源最短路径，首先，得到节点u与图G中其他节点最短路径，然后根据参数r和s生成PDNS(u,r,s)。以图1中节点1为例并假定r=2、s=2，根据PDNSA算法第1行，得到节点1的所有最短路径：<1,4>、<1,4,2>、<1,4,2,3>、<1,4,5>、<1,4,5,6>、<1,4,5,7>,则此时N1(1)={1,4}；节点1的r范围可达，则是指与节点1最短路径长度不大于r的节点，由上述最短路径可知N2(1)={1,4,2,5}；N*(1)则是所有最短路径中的节点，N*(1)={1,4,2,3,5,6,7}；此时，N2(1)-N1(1)={2,5}，包含2个节点(大于等于S)，因此，PDNS(1,2,2)={2,5}。

为了保护节点的可达性，提出基于UD&OP策略的RPP算法，其基本思想是：首先，为图G的每条边以概率p和(1-p)赋予权重1或-1；其次，若边的权重值为-1，则将从图G中移除，并将和相应的PDNS(u,r,s)存放在ECN表中，得到初始匿名图G*；最后，将ECN表中的边标记为“unanonymized”，然后做以下操作：

(1) 判断其PDNS(u,r,s)中是否存在节点w，节点w在匿名图G*可达v，若存在则向G*添加链接。

(2) 若PDNS(u,r,s)中不存在节点w，判断G*中是否存在其他节点s可达v，若可达，将链接添加到G*。

(3) 若(1)和(2)均为成功，则添加伪节点t，并向G*添加边和。

(4) 经过(1)、(2)、(3)后，将边标记为“anonymized”，并从ECN表中移除，得到新的匿名图G*。处理ECN中下一条标记为“unanonymized”的边。

(5) 重复步骤(1)、(2)、(3)、(4)直到ECN表为空，得到最终的匿名图G*。

RPP算法的具体过程如算法2所示。

算法2Reachability Preserving Perturbation

Input: 社会网络图G=(V,E)；链接保留概率p；参数s；参数r，r≥2。

由于清洗节气门后，没有对其进行匹配，所以导致进气量、喷油量、点火正时严重偏离了正常范围。该发动机控制系统的控制方式比较奇特。由于积炭导致的节气门开度过大，发动机电脑记忆的初始节气门位置就会过大，在针对节气门进行清洗作业后，如果没有进行节气门初始化的话，其节气门开度不会自动减小，使通过节气门的进气量过大，相应的喷油量也会过大，导致清洗后的短时间内发动机转速急剧增加，达到2 000r/min左右，但由于此时的加速踏板位置信号处于全闭状态，电脑又不允许出现转速过高的情况。

Output: 匿名图G*。

1:PDNSA(G);

//利用算法1得到所有节点的PDNS(u,r,s)。

2: 对图G中边以概率p和(1-p)赋予权重1或-1。

3: 移除图G中所有权重为-1的边得到初始匿名图G*,并将边与对应的PDNS(u,r,s)存入ECN表。

4:ifECN非空

5:forfirstinECN

//处理ECN表中第一条边。

6:ifwPDNS(u,r,s)满足w v

//若PDNS(u,r,s)中存在w可达v

7:Add to G*;

//添加边到G*

//G*存在其他节点s可达v

9:AddtoG*;

//添加边到G*

10:else

11:AddNewnodettoG*andadd, to G*;

//添加伪节点和伪边

12:updataG*;

//匿名完成后，更新匿名图G*

13:removefromECN;

//从ECN删除边

14:else

15:returnG*

下面以图1为例，叙述RPP算法的边扰动过程，并假设r=2、s=2，RPP算法通过1-3行，得到如图3所示的ECN表和初始匿名图G*。

图3 ECN表和匿名图G*

RPP算法执行第4行，由于ECN，则扰动第一条边<1,4>，其PDNS(1,2,2)={2,5}，从G*中可知，此时节点5可达节点4，则添加<1,5>到G*并将<1,4>从ECN表中删除，得到新的匿名图G*,如图4所示。

图4 新的ECN表和匿名图G*

图5 最终匿名图G*

此时ECN非空集，算法执行4～12行，由于<3,6>所对应的PDNS(3,2,2)={2,7}并没有节点可达6，因此需要判断G*是否有节点可达6，此时图G*中节点1、4、5都可达6，考虑到最短路径的变化，选择节点5，因为这样才使得节点3和6的最短距离变化最小，添加<3,5>到G*。同理，处理边<2,3>，此时{4,6}和G*中没有可达3的节点，因此向G*添加伪节点8，并添加边<2,8>和<8,3>，得到最终的匿名图G*，如图5所示。

4 实 验

实验对RPP算法进行性能分析和评价。实验采用SNAP网站提供的两个真实社会网络图数据集Wiki-Vote和p2p-Gnutella04进行分析和测试。

4.1 实验数据集及实验环境

Wiki-Vote是维基百科2008年1月份的投票数据，其中有向边表示用户u向用户v投出选票，Wiki-Vote数据集包含7 115个节点，103 689条链接；p2p-Gnutella04数据集来源于Gnutella网络2008年8月4日以来的数据，节点代表网络中的主机，有向边表示主机之间的链接，p2p-Gnutella04数据集共包含10 876个节点和39 994条边。

实验将文献[1]的匿名算法实现并记作NR，用于对比RPP算法。实验的软硬件环境如下：

(1) 硬件环境：Intel Core i7-2720QM，CPU 2.2 GHz，16 GB RAM，120 GB SSD。

(2) 操作系统：Win10 专业版。

(3) 编程语言：Python 3.5。

4.2 算法性能分析

实验测试了算法执行时间随参数p以及r值变化的情况，实验结果如图6所示，其中“X-NR”表示用文献[1]中匿名方法处理数据消耗的时间，“X-RPP”是利用RPP算法匿名数据消耗的时间，p表示边的保留概率，r表示邻居半径。从图6中可以看出，NR算法和RPP算法匿名图所消耗的时间会随r值的变大而增加，随着边保留概率p的增大而降低。从实验结果可知，当边的保留概率大于0.5时，RPP算法在执行效率上接近与NR算法，而当r不大于4时，两者的执行效率差别也不大。

(a) 时间随参数p值变化的情况

(b) 时间随参数r值变化的情况图6 时间随参数p以及r值变化的情况

4.3 数据可用性分析

实验从添加节点数目、节点的度中心性以及接近中心性三方面测试RPP算法在数据可用性上的表现。节点的度中心性是社会网络分析中衡量节点中心性最直接度量指标，一个节点的度越大，说明此节点在社会网络中的度中性越高；节点的接近中心性，是衡量节点与社会网络中其他节点亲密度的指标，节点的接近中心性越高，说明节点传递消息越迅速。实验通过计算原始图以及扰动图中的节点排名等级列表的斯皮尔曼相似性[16]来判断度中心性和接近中心性的变动情况，相似性值越大，数据可用性越高。

为了评估匿名图G*中新添加的节点所占的比例，定义节点添加率=Na/N*，其中Na是添加的节点数目，N*是匿名图G*中的节点数目。图7给出了两个数据集随着保留概率p和邻居半径r变化添加节点数目的变化情况。实验结果显示,添加的节点数目随着保留概率p的增大而减少,但随着参数r的增而增多。由此可知，适当选取p和r的阈值能有效降低节点的添加率，提高数据的可用性。

图7 p和r改变时添加节点数变化情况

图8和图9分别展示了，数据集Wiki-Vote和p2p随参数p、r变化的接近中心性的变化情况，其中NR是利用文献[1]处理的结果，“RPP”是利用所提出的RPP算法所得到的结果。可以看出，两种方法的变化趋势基本一致，都随p的增大而提高可用性，随r的增大可用性降低。RPP算法NR算法基本持平，部分略高于后者，同NR算法相比，在接近中心性方面表现更好。

图8 数据集wiki-vote随参数p变化的接近中心性的变化情况

图9 数据集p2p随参数r变化的接近中心性的变化情况

从实验结果中可以看出，RPP算法要略低于NR算法，这是因为RPP算法为了保持节点间的可达性，向图中添加了一定量的伪节点，这些伪节点致使节点的度中性有所降低。但随着边保留概率p的增大，RPP算法逐渐逼近NR算法，这是因为随着p的增大，添加的节点数目逐渐减少的原因。

5 结 语

针对图扰动过程中，匿名图在节点间可达性查询可用性低的问题，提出一种“统一删除，顺序扰动”的局部邻居随机的社会网络隐私保护方法，该方法通过统一删除需要扰动的边，并将边连同假目标节点集存放于ECN表中，然后扰动ECN表中的边，达到保持节点可达性的目的。下一步将对RPP算法做进一步优化，提高算法的执行效率，减少伪节点的添加数目。