基于k-同构和局部随机化的隐私保护方法

葛丽娜，张 静，刘金辉，王 红

(1.广西民族大学信息科学与工程学院，广西南宁530006；2.广西民族大学东盟研究中心(广西科学实验中心)，广西南宁530006)

基于k-同构和局部随机化的隐私保护方法

葛丽娜1，2，张 静1，2，刘金辉1，2，王 红1，2

(1.广西民族大学信息科学与工程学院，广西南宁530006；2.广西民族大学东盟研究中心(广西科学实验中心)，广西南宁530006)

在社会网络数据被大量收集和发布的过程中存在隐私信息泄露的情况，社会网络隐私保护问题引起了人们的关注。本文针对单一方式的社会网络隐私保护方法中数据损失程度较大及数据可用性较低等方面问题，优化了k-同构算法和随机化算法，设计基于k-同构和局部随机化的隐私保护方法。实验结果表明：本文方法可以有效减少信息损失，保护用户隐私信息，对于衡量图谱中的调和平均最短距离、子图中心度2个方面均有较好效果，提高了发布数据可用性，可以抵御图结构信息背景知识再识别攻击。

社会网络；隐私保护；结构信息；k-同构；随机化

0 引言

社会网络是由许多节点(个体或组织)构成的一种社会结构，代表社会之间关系。它把陌生人到有亲密关系的各种人或团体串连起来[1]。社会网络隐私保护是以原始的网络数据作为基础，采用适当的信息隐匿技术对数据进行处理，阻断敏感数据和用户信息间的关系，然后将处理后的数据对外发布，保护用户部分信息，同时，保障这些信息具有可用性。

隐私保护技术对社会网络用户、网络提供商和网络数据使用者等各方都有积极意义。对于网络用户，充分保障其隐私信息，避免因为数据发布而带来信息泄漏；对于网络服务提供商，可以安全地把数据发布给政府或合法数据挖掘者研究，充分发掘数据的潜在价值；对于数据使用者，既可以获得有价值的数据，又不会因为数据涉及隐私而无法分析。

1 社会网络隐私保护相关技术

1.1 社会网络相关定义描述

社会网络中存在于用户个体直接或间接的关联关系常会被认为是更具潜力和有意义的信息，需要重点保护。通常采用图论理论对社会网络进行构建描述[1]，网络图数据采用邻接矩阵形式予以表示。

定义1[2]k-security(k-安全)：社会网络图为G=(V，E)，其发布网络图为GP=(VP，EP)，在图G中∀v⊂V，假设节点存在唯一信息(vertex information，VI)表示为VI(v)，对于图G中任意的目标节点x和y，攻击者均能通过某种方式得到目标对象的邻域攻击图Gx及Gy。假设在发布网络图过程中满足2个条件：①攻击者从GP和Gx(Gy)确定x(y)对应的节点vx(vy)与VI(v)关联的概率不超过1/k；②攻击者从图GP、Gx、Gy确定目标x与y由特定长度的路径相连的概率不超过1/k。则发布网络图GP是k-security。

定义2[2]k-isomorphism(k-同构)：将社会网络图G划分k个子图分别为G1， G2， G3，…， Gk，如果网络图G中任意2个子图没有任何交集，即Gi∩Gj=∅，i≠j，且图Gi与图Gj是同构的，则图G是k-isomorphism。

定理1[3]若存在社会网络图G ={G1，G2，G3，…，Gk}，满足k-isomorphism，那么其也是k-security。

社会网络还使用0-1矩阵形式表示，记为A，其特征值为λi(i=1，…，n)，且λ1≥λ2≥…≥λn，特征值λi的特性向量为ei。网络图谱用集合{λ1，λ2，…，λn}表示。最大特征值λ1即图谱半径，谱半径就是网络图的谱性质，也是邻接矩阵的谱性质。谱性质是衡量网络图结构性能的重要指标。

社会网络图的对角矩阵用D表示，即为社会网络的度序列，也称为图的度矩阵，其元素dij表示第i个节点度数，有dij=0(i≠j)。社会网络图的拉普拉斯矩阵表示为L=D-A。其中L的特征值为μi，μ1≤μ2≤…≤μn，特征值μi的特征向量为ui。网络图的拉普拉斯谱用集合{μ1，μ2，…，μn}表示。次最小特征值为μ2，对应的特征向量为u2=(y1，y2，…，yn)T，拉普拉斯谱中μ2用来判断一个社会网络图中的连通性能，若μ2的值越大，则此网络图的连通性越差。

假设定理3中的矩阵E为需要使用到的扰动矩阵，本文提出的局部随机化方法是通过扰动矩阵E影响网络图。

1.2 社会网络隐私攻击类型

背景知识攻击是对社会网络的一种主要攻击类型，攻击者通过某渠道获得可作为参考的信息，分析处理从而获得目标对象的相关标识信息，以攻击目标对象的隐私信息。通常，节点的存在性、节点连接关系、边权值、子图结构等都被看作是背景知识。相对于主动和被动攻击，背景知识攻击情况更为复杂，攻击者可以通过许多途径获得目标对象的有效信息。

另外一种主要攻击形式是再识别攻击[6]，它针对已经发布的社会网络，通过一些技术重新识别以获得目标用户的相关隐私信息，通常分为基于属性和基于结构的再识别攻击。基于结构知识的再识别攻击，是社会网络中特有的攻击类型，在社会网络拓扑结构信息中，攻击者可以通过节点度、领域和子图等信息重新识别出目标用户隐私信息。本文研究的隐私保护方法是针对此类型攻击提出的。

1.3 隐私保护方法性能衡量

1.3.1 信息损失度量

信息损失度量是分析发布的社会网络图数据是否可被使用的重要指标。信息损失度越小，则可用性和有效性越高。

当对网络图的拓扑结构信息进行增加或删除节点和边的操作时，会产生信息损失。网络结构信息损失度量表示为发布前后网络图的节点和边数量之间的变化程度[7]，记作ILD。

设社会网络图为G=(V，E)，其发布网络图为GP=(VP，EP)，则信息损失度ILD如公式(1)：

ILD(G，GP)=|(V∪VP)-(V∩VP)|+|(E∪EP)-(E∩EP)|，

(1)

其中|(V∪VP)-(V∩VP)|、|(E∪EP)-(E∩EP)|分别表示网络图发布前后节点和边数目的变化。

1.3.2 图的调和平均最短距离

图的调和平均最短距离用于分析与衡量隐私保护方法对网络图的结构特性的影响，用h描述如公式(2)：

(2)

其中dij表示节点i、j之间的最短限度距离，调和平均最短距离h的倒数描述了这个网络全局效应。当h-1=0时，图中的所有节点互相之间没有联系；当h-1=1时，此网络图表示一个完全的网络图。

1.3.3 子图中心度

图的子图中心度(subgraph centrality，SC)是衡量网络图结构特性的一个重要指标，主要用来量化网络图中的节点在子图中所处的中心位置，表示如公式(3)：

(3)

2 基于k-同构和局部随机化的隐私保护方法研究

针对攻击者利用网络图结构背景知识进行再识别攻击，本文改进了k-同构隐私保护方法和局部随机化方法，设计社会网络数据发布中隐私保护方法。该方法有效结合不同模型的优点，可以较好抵御再识别攻击。

优化k-同构隐私保护方法是对GSPB K+-isomorphism匿名方法[3]进行优化，将网络图划分为3部分分别进行操作，并且添加了判断子图是否满足同构的步骤。局部随机化方法是对基于图谱的随机化方法[8]进行改进，更适用于局部网络图操作，每步完成交换边处理后，均重新计算网络图的邻接矩阵最大特征值等，能较好地控制网络图的谱半径。

2.1 优化的k-同构隐私保护方法

优化的k-同构隐私保护算法主要包含下面3个方面：

①子图同构匿名方法。

引用文献[9]中的Fresp方法处理子图同构匿名。发布前，利用优化频率子图将社会网络图划分为k个彼此同构的子图，既提高匿名效果又避免网络图中数据大量丢失。

②判断子图同构方法。

采用哈希编码方法[10]判断划分子图集同构处理后是否满足同构。通常由于子图的结构信息不同，将子图中的节点与其邻接节点通过一个迭代哈希编码函数处理，之后子图的节点编码值也可能不同。算法具体描述过程如下：

算法1 判断子图同构的哈希编码方法。

输入：社会网络图G=(V，E)中2个子图g1=(V1，E1)， g2=(V2，E2)，子图中节点数为n。

输出：社会网络2个子图是否满足同构。

1. 随机选取4个常量a、b、c、d和迭代次数T；

2. 对2个子图g1=(V1，E1)， g2=(V2，E2)节点分别计算节点哈希编码值，即执行步骤3～9；

3. 初始化f0(i)=1， 其中i=1，2，…，n；

4. for(i=1； i<=n， i+ +)

5. for(j=1； j<=T； j+ +)

//y为节点i的邻居节点，fj(i)为节点i的迭代j次的哈希编码函数；

7. End for

8. h(i)=fT(i)； //节点i迭代T次哈希编码值存放函数h(i)中；

9. End for

10. 生成哈希序列分别为h1={h1(1)，h1(2)，…，h1(n)}，h2={h2(1)，h2(2)，…，h2(n)}；

11. if(h1=h2)输出表示子图同构；else输出不同构。

通过此方法最大限度地保证发布网络图是满足子图同构的，也就是满足k-security的。

③优化k-同构隐私保护方法。

优化的k-同构隐私保护方法是对GSPB K+-isomorphism匿名方法进行的优化。首先，深度优先搜索社会网络图，找出满足节点数的k个连通子图数集，存放在FSG中，利用Fresp算法[9]对FSG处理形成同构子图集，并使用算法1对其进行同构判定。然后，对余下的节点数不满足要求的，重新划定匿名参数x。找出x个连通子图的集合，存放于FSG′中。将这部分子图中节点数同前面的子图节点数做比较，若少于或多于FSG中子图节点数，则增加或删除适量节点以保持相同，更新子图数集FSG。再用Fresp算法[9]对子图数集FSG进行同构处理，并使用算法1对其进行同构判定。最后，仍有一小部分不满足匿名条件的子图，存放在剩余子图集RSG中。具体过程描述如下：

算法2 优化的k-同构隐私保护方法。

输入：社会网络图G，匿名参数k，图G的节点总数为N。

输出：匿名网络图GP。

1. GP=∅； //初始化匿名的网络图。

2. N′=[N/k]，NL=N-N′×k； //处理后网络图中每个子图含有N′(取整)个节点，划分后余下节点数为NL；

3. for (i=1； i <=k； i + +)

4. 深度优先遍历图G，找出满足节点数为N′个的连通子图gk(i)；

5. 将gk(i)入FSG集合中；

6. End for

7. 用子图同构匿名Fresp方法同构数据集FSG中的连通子图gk(i) (i=1，2，…，k)；

8. 用算法1对步骤7中子图两两进行判断；

10. NL个剩余未处理节点以及其相连的边存放到图G2中；

11. x=[N′/NL]；

13. for (j=1； j<=x； j+ +)

15. 连通子图gx(j)存储在FSG′集合中； //连通子图gx(j)的个数为x；

18. else

20. End if

21. End for

22. 采用子图同构匿名Fresp方法同构数据集FSG′中的连通子图gx(j) (j=1，2，…，x)；

23. 采用算法1对步骤22中子图两两进行判断；

24. 经判断满足同构的子图存放到图G″P中；

25. N″L个剩余节点以及其相连的边存放数集RSG中；

算法2中匿名参数k值选取十分重要，若网络图的总节点数被k整除，则算法只需执行前面的部分操作形成同构子图，但在这种情形下易受背景知识攻击，因此本文只考虑不被整除的情况。同理在计算x时，剩余节点数不能被x整除。

2.2 局部随机化方法

算法3 局部随机化方法。

输入：社会网络图G，扰动次数F，扰动矩阵E。

输出：匿名网络图G″P。

1.求出图G邻接矩阵A、对角矩阵D、拉普拉斯矩阵L；

2.计算矩阵A最大特征值和特征向量(λ1，e1)，矩阵L次小特征值和特征向量(μ2，u2)，扰动矩阵E特征值εi；

3.步骤4～14重复F次；

5. 在G中随机选择边(t，w)；

8. 交换(t，w)，(u，v) to (t，v)，(u，w)；

9. 存放网络图G″P；

10. else

12. 交换(t，w)，(u，v) to (t，v)，(u，w)；

13. 存放网络图G″P；

14. End if

15. 返回发布网络图G″P。

2.3 基于k-同构和局部随机化的隐私保护方法设计

为了解决单一模型对网络图隐私数据保护程度不足、数据可用性低、易受背景知识再识别攻击等方面问题，将2.1及2.2节中算法进行结合，提出基于k-同构和局部随机化的隐私保护方法(简写为BK-R)。具体步骤如下：

算法4 基于k-同构和局部随机化的隐私保护方法。

输入：社会网络图G，匿名参数k，扰动次数F，扰动矩阵E。

输出：匿名网络图GP。

2.优化k-同构：根据k采用算法2获得同构子图集存放到网络图G″P，将剩余小部分数据集存放到RSG中。

4.发布匿名的网络图GP= {G″P， GP2}。

2.4 理论分析

算法在初始阶段采取了简单匿名隐私保护隐匿节点的标签信息，使攻击者无法从中直接获得攻击对象的标签信息。之后算法对网络图中节点和边进行部分节点或边增删操作，如此一来，即使攻击者在网络图发布之前已经创建并标识与目标对象有联系的节点或边，在发布的网络图中也不能轻易获得标识的节点或边，目标对象不能被轻易识别出。且即使攻击者在社会网络对外发布前对目标对象的节点做了标记，攻击者想要通过之前标记的节点对发布网络图进行攻击也是不容易的，可以较好地抵御简单主动攻击和被动攻击。

本文对子图进行了同构处理，同构子图在图的结构上是无法直接区分的，网络图数据被辨识的几率低于1/k，满足k-匿名且满足k-security原则。随后进行局部随机化，仅对部分原网络图进行交换边处理，这部分的网络图结构保持较稳定状态。相对于单一使用某种隐私保护模型，本文方法从理论上可以更有效抵御基于图结构信息知识背景再识别攻击。

3 实验结果及分析

实验编程语言为C++语言，运行平台为Visual C++ 6.0。所需数据集采用UCINET 6软件，定义一个小型的节点数为238，边数为670的社会网络，将图结构以矩阵数据表示。利用UCINET软件构造相应的社会网络图，然后，对信息损失度、图调和平均最短距离及子图中心度进行分析。

3.1 信息损失度量

下面对k-isomorphism方法[2]、GSPBK+-isomorphism方法[3]及本文方法BK-R的信息损失度进行比较分析，匿名参数k分别取值为3、5、10、15、18。

图1 不同k值下不同方法信息损失程度Fig.1 Loss of information measure under different values of k

由图1得出，随着k值增加，3条曲线(信息损失度)均趋于线性增长。在k值取值为3时，k-isomorphism方法信息损失度最低。当k取值大于3时，k-isomorphism方法信息损失量急剧上升，信息损失度较大，GSPBK+-isomorphism方法和本文方法信息损失量平缓上升，且GSPBK+-isomorphism方法曲线增幅大于本文方法的增幅。相同k值时BK-R在信息损失度量上较其他2种方法低，且其信息损失度一直低于20%。

BK-R方法随着k值增大，网络图划分的子图个数越少，划分后子图进行同构隐匿处理，用户节点或边被识别几率就越低，所添加或删除节点和交换边的数量随着k值增大而减少，即信息损失程度较其他方法更低，因此BK-R数据的可用性较其他单一方式的隐私保护方法可用性更高。

3.2 图的调和平均最短距离、子图中心度

选取不同扰动次数F值，对BK-R方法与无任何限制条件的随机化方法(简写为NR)的调和平均最短距离及子图中心度进行实验比较分析。

图2 调和平均最短距离hFig.2 The shortest distance of harmonic mean value

图3 子图中心度SCFig.3 The values of subgraph centrality

由图2和图3看出，随着扰动次数F增加，BK-R方法和NR方法的调和平均最短距离h曲线和子图中心度SC曲线均整体下降。在F值较小时，2种方法的h值和SC值下降幅度均很大，且NR方法的h值和SC值比本文方法下降幅度更快。当F值增大时，2种方法的h曲线和SC曲线均变得较平缓，表明2种方法发布的网络图的结构特性保持稳定状态。当F取同一值时，NR方法的h值和SC值都比本文方法小很多。

本文方法比NR方法对发布的网络图的结构特性改变程度更小，不会牺牲太多信息。通过将网络图的谱半径大小控制在一定范围内进行局部随机化处理，即使随机化过程中图的部分结构特性信息有所改变，但整体而言本文方法能够较好保持网络图的结构特性，有效保护了用户的结构特性信息，相对于NR方法能更好地提高发布网络图结构特性数据的可用性。

4 结束语

本文结合优化的k-同构和改进的随机化这2种模型的优点，提出基于k-同构和局部随机化的隐私保护方法。将2种模型有效结合使用，对不同网络图数据集采取不同的模型，使得处理的结果满足用户匿名需求。通过理论与实验分析表明：本文方法较单一使用某种隐私保护方法在数据可用性方面更优，且可以抵御背景知识再识别攻击，有效保护网络图的结构特性信息。

社会网络数据发布中隐私保护方法仍然面临许多严峻考验。现实中的社会网络十分复杂，网络图数据信息呈现指数级增加，本文研究方法的执行效率、数据处理能力还不能满足大型社会网络的实际应用需要。下一步工作将提出改进的方法，应用于数据量更庞大的现实社会网络中。

[1] 刘军. 社会网络分析导论：An introduction to social network analysis[M].北京：社会科学文献出版社， 2004：1-4.

[2] CHENG J， FU A W， LIU J. K-isomorphism：privacy preserving network publication against structural attacks[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. New York：ACM， 2010：459-470.DOI：10.1145/1807167.1807218.

[3] WU Hongwei，ZHANG Jianpei，WANG Bo， et al. K+-isomorphism：privacy preserving publication against structural attacks in social networks[J]. International Journal of Advancements in Computing Technology， 2012， 4(22)：154-162. DOI:10.4156/ijact.vol4.issue22.18.

[4] 孙继广. 矩阵的扰动分析[M]. 2版. 北京：科学出版社， 2001：163-190.

[6] 刘向宇， 王斌， 杨晓春. 社会网络数据发布隐私保护技术综述[J]. 软件学报， 2014， 25(3)：576-590. DOI:10.13328/j.cnki.jos.004511.

[7] LIU Kun， TERZI E. Towards identity anonymization on graphs[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York：ACM， 2008：93-106. DOI:10.1145/1376616.1376629.

[8] 王小号， 耿惠， 陈铁明. 基于谱约束和敏感区划分的社会网络隐私保护扰动方法[J]. 计算机应用， 2013， 33(6)：1608-1611, 1614. DOI:10.3724/SP.J.1087.2013.01608.

[9] 张晓琳， 李玉峰， 刘立新， 等. 社会网络隐私保护中K-同构算法研究[J]. 微电子学与计算机， 2012， 29(5)：99-103.

[10] TANG Chenxing， WANG Xiaodong. Preserving privacy in social networks against subgraph attacks[C]//2010 IEEE International Conference on Intelligent Computing and Intelligent Systems. Piscataway，NJ：IEEE Press， 2010：154-158. DOI:10.1109/ICICISYS.2010.5658516.

Nanning Guangxi 530006，China)

(责任编辑 黄 勇)

Privacy Preserving Method Based onk-isomorphismand Local Randomization

GE Lina1，2， ZHANG Jing1，2， LIU Jinhui1，2， WANG Hong1，2

(1.College of Information Science and Engineering， Guangxi University for Nationalities， Nanning Guangxi 530006，China；2. China-ASEAN Study Center (Guangxi Science Experiment Center) of Guangxi University for Nationalities，

In the process of social network data collection and release, privacy information leakage often takes place so that social network privacy protection has aroused people’s concern. In order to solve the problem of significant data loss and poor availability of data in a single mode of social network privacy preserving method ，ak-isomorphism and locally randomized method of privacy preserving is proposed， which included the optimizedk-isomorphism method and locally randomized method. The experimental results show that the proposed method in this paper could effectively resist information loss， and has good performance in measurement of harmonic mean of the shortest distance and sub-graph centrality of information within graph. It can protect user’s privacy information effectively and improve the usability of data issued， and also can effectively resist recognition attack from attacker based on background knowledge of graph structure.

social network； privacy preserving； structure information；k-isomorphism； randomization

10.16088/j.issn.1001-6600.2016.04.001

2016-06-19

广西高等学校优秀中青年骨干教师培养工程资助项目(桂教人[2013]16 号)；国家自然科学基金资助项目(61462009)；广西民族大学中国-东盟研究中心(广西科学实验中心)开放课题资助项目(TD201404)

葛丽娜(1969—)，女，广西环江人，广西民族大学教授，博士。E-mail：66436539@qq.com

TP309

A

1001-6600(2016)04-0001-08