保持结点间可达性的社会网络图匿名技术

刘向宇，安云哲，周大海，夏秀峰

(沈阳航空航天大学 计算机学院，沈阳 110136)



信息科学与工程

保持结点间可达性的社会网络图匿名技术

刘向宇，安云哲，周大海，夏秀峰

(沈阳航空航天大学 计算机学院，沈阳 110136)

为了保护社会网络隐私信息，提出了多种社会网络图匿名化技术。图匿名化目的在于通过图修改操作来防止隐私泄露，同时保证匿名图在社会网络分析和图查询方面的数据可用性。作为图查询操作的基础，可达性查询是衡量图数据可用性的一项重要指标。然而，图匿名会对结点间的可达性造成影响，导致较大的可达性信息损失。为了保持匿名图中结点间的可达性，提出可达性保持图匿名化算法(简称RPA算法)。通过生成可达性保持最小子图并在图匿名化过程中保持该子图的完整性，RPA算法实现了在匿名图中保持结点间的可达性。基于真实数据集通过大量实验测试和分析，验证了RPA算法可以保证在匿名图中进行可达性查询的高准确度。

社会网络；隐私；图匿名；可达性

随着社会网络的快速发展和普及，社会网络中隐私信息的安全性成为数据隐私保护研究的热点问题。为了保护社会网络隐私信息，提出了多种社会网络图匿名化技术[1-4]。图匿名化目的在于通过图修改操作来防止隐私泄露，同时保证匿名图在社会网络分析和图查询方面的数据可用性。

结点间的可达性是一项重要的图查询操作，包括查询两个结点是否存在路径可达[5-6]或者两个结点是否在一定距离阈值内可达[7]；可达性也是衡量图数据可用性的重要指标。在社会网络中，可达性查询操作更加频繁。例如，很多社会网络(Facebook，QQ朋友网等)均支持人脉联系查询：输入用户u和v，返回u、v之间的可达路径以及路径上包含的用户。显然，此种人脉联系查询的本质是结点间的可达性查询操作。很多社会网络应用基于结点间的可达性来进行好友推荐[8-9]，提高社会网络的粘度和用户活跃度。因此，保持社会网络中结点间的可达性具有实际意义。然而，在文献[10]中指出，由于当前图匿名技术没有考虑图修改操作对于结点间可达性的影响，从而导致结点可达性信息损失很大。

图1 虚构微博网络G及结点的度

然而，图G1、G2在保持结点间可达性方面具有不同效果。给定图G和距离阈值d，Rd(G)表示G中所有最短路径长度≤d的结点对集合；距离阈值d表示用户感兴趣的可达性查询路径长度。匿名化G得到匿名图Gk，则Rd(Gk)和Rd(G)的相近程度衡量了Gk在d-可达性查询上的数据可用性。在图2中，当距离阈值d=2时，G1比G减少了4个2-可达结点对〈v1,v7〉、〈v3,v7〉、〈v4,v7〉和〈v4,v12〉，增加了一个2-可达结点对v9,v11；而G2和G具有相同的2-可达结点对集合，显然G2更好地保持了图G中结点间可达性。已知图G和可达性查询距离阈值d，本文期望构建G的k-度匿名图Gk，使得Rd(Gk)和Rd(G)尽可能相近。

图2 图G的两个2-度匿名图

1 背景知识和问题定义

在本文中，将社会网络表示为有向图G=(V，E)，V(G)和E(G)分别表示G的结点集和边集。结点对(u,v)表示从结点u指向v的边；边(u,v)称为u的出边、v的入边；v是u的出边邻居，u是v的入边邻居。结点u的入边数目是u的入度，记作din(u)；u的出边数目是u的出度，记作dout(u)；结点u的度以(din(u),dout(u))的形式来表示。

本文假设攻击者发动度隐私攻击，即将攻击目标的出度和入度作为背景知识进行结点身份识别，下面给出社会网络隐私保护模型。

定义1.k-度匿名. 已知图G(V,E)和正整数k，对于∀v∈V，如果G存在至少k-1个其他结点与v具有相同的出度和入度，则G为k-度匿名图。

例如，图2中的G1和G2均为2-度匿名图。

数据发布者可以根据图查询和分析需求来选择合适的d值，阈值d反映了对于保持匿名图中结点间可达性的要求。通常情况下，d值不会很大，这是因为根据社会网络小世界理论(亦称六度分隔理论)，任意两个结点之间所间隔的结点通常不会超过六个，针对距离较远的两个结点间关系的研究意义不大。在社会网络中，d-可达性是结点邻居查询、可达性查询、路径计算、聚集查询等图查询操作的基础，因此保持匿名图中结点间的d-可达性具有实际意义。

已知图G(V,E)，正整数k和阈值d，本文研究如何生成k-度匿名图Gk(Vk,Ek)，使得Gk较好地保持G中结点间的d-可达性。匿名过程中仅考虑结点添加操作，即V⊆Vk。问题1给出了可达性保持图匿名化问题。

问题1.可达性保持图匿名化问题.已知图G(V,E)，正整数k和d，构建一个k-度匿名图Gk(Vk,Ek)使得匿名信息损失C(G,Gk)最小化，其中C(G,Gk)包含三部分：

(1)d-可达性信息损失；

(2)结点修改信息损失；

(3)边修改信息损失。

在问题1中，d-可达性信息损失采用|R(G)-|Rd(G)|+|Rd(G)-R(G)|进行衡量，即在Rd(G)中增加和减少的d-可达结点对数目；结点和边修改信息损失分别通过结点、边修改数目来评估。

定理1.可达性保持图匿名化问题是NP-hard问题。

定理1可以通过归约NP-complete问题k-DIMENSIONAL PERFECT MATCHING[12]来进行证明。

2 可达性保持最小子图

为了保持匿名图中结点间的d-可达性，可以生成保持发布图可达性的最小子图，并在图匿名化过程中保持该子图的完整性。基于此思想，本节提出d-可达性保持最小子图及其生成算法。

2.1 可达性保持子图

定义3.可达性保持子图. 已知图G(V,E)和正整数d，假设G′(V′,E′)是G的一个子图，并且满足V′=V和E′⊆E；对于G中的任意d-可达结点对u,v，如果在G′中u到v仍然符合d-可达，则G′是G的一个d-可达性保持子图(d-Reachability Preserving Subgraph, 简称d-RPG)，记作G′dG。

例如，对于图1(a)中的G，图3显示了G的两个3-RPG，即G33G和3G。为了保证图匿名的低信息损失，希望找到G的最小d-RPG。

图3 有向图G的两个最小3-RPG

定义4.可达性保持最小子图.已知图G(V,E)和正整数d，如果GddG并且Gd的任意子图G′均不满足G′dG，则Gd是G的d-可达性保持最小子图，记作最小d-RPG。

定理2. 已知图G(V,E)和正整数d，生成G的最小d-RPG是NP-hard问题。

可以通过归约NP-complete问题DIRECTED HAMILTONIAN CIRCUIT[14]来对定理2证明。

2.2 生成最小d-RPG

已知图G(V,E)和正整数d，算法1给出一种最小d-RPG生成算法。

算法1. 生成最小d-RPG.

输入：图G(V,E)和正整数d

输出：最小d-RPGGd

(1)Gd←G；

(2)For each (u,v)∈Gddo

(3)G′←Gd{(u,v)}；

(4) IfR(G′) =R(Gd) then

(5)Gd←Gd{(u,v)}；

(6) end if

(7)end for

(8)returnGd.

算法1首先利用G来初始化Gd(1行)。对于Gd中的每条边(u,v)，检查该边是否可以从Gd中删除(2-4行)。在Gd中删除边(u,v)时，会发生两种情况：(1)Rd(Gd)保持不变；(2)Rd(Gd)丢失一些d-可达结点对。如果Rd(Gd)保持不变，则边(u,v)可以删除并将其从Gd中删除(4-5行)；如果Rd(Gd)发生变化，则边(u,v)不可删除。算法1为Gd中每条边执行验证和删除操作后，输出Gd作为结果。显然，算法1生成的Gd是G的一个最小d-RPG。

3 保持结点间可达性图匿名化算法

本节提出一种保持结点间可达性的图匿名化算法(Reachability Preserving Anonymization,简称RPA算法)。RPA算法通过在匿名过程中保持d-RPG的完整性，从而保持匿名图中结点间的d-可达性。首先介绍RPA算法整体框架，然后介绍算法具体细节。

3.1 RPA算法整体框架

算法2显示了RPA的整体框架。已知图G(V,E)及其d-RPGGd、正整数k、信息损失权重参数α和β，RPA算法将G匿名化为k-度匿名图Gk。

算法2. 可达性保持图匿名化(RPA)算法.

输入：图G(V,E)及其d-RPGGd，正整数k，匿名信息损失权重参数α和β

输出：k-度匿名图Gk(Vk,Ek)

(1)基于Gd初始化G中结点标签和边标签；

(2)repeat

(3)Seed←SearchSeedVertex(G)；

(4)VA←AnonymizationVertexSet(G,Seed,k,α,β)；

(5) if |VA|

(6) 将Seed标记为”postprocessing”；

(7) else

(8) (din,dout)←OptimalDegree(VA,α,β)；

(9) for each vertexv∈VAdo

(10) 将结点v匿名化为度(din,dout)；

(11) end for

(12) end if

(13)untilUnAnonymized(G)<2k-1；

(14)匿名化”unanonymized”和”postprocessing”结点；

(15)基于G中结点和边标签生成Gk；

(16)returnGk.

与传统图匿名算法中直接进行图修改操作不同，算法2通过标记G上的结点和边标签来进行匿名(2-13行)，当G中结点均标记为”anonymized”时，基于结点和边上的标签来生成匿名图Gk(15行)。在匿名化过程中，算法2首先对G中结点标签和边标签进行初始化(1行)，结点标签初始化为”unanonymized”，存在于Gd中边的标签初始化为”added”，其他边标签初始化为”un-added”。算法2在标记”unanonymized”的结点中选择种子结点Seed(3行)。其中，匿名信息损失权重参数和由数据发布用户根据数据发布用途和可用性来进行设置，参数是用于衡量边修改信息损失的权重参数，是衡量d-可达性信息损失的权重参数。基于种子结点Seed生成匿名结点集VA(4行)，其中VA包含k个结点并且结点具有相近的度。对于某些种子结点Seed，生成的VA包含结点数目可能小于k，将此类Seed结点标记为”postprocessing”(5-6行)。基于VA和参数α、β，计算最优结点度(din,dout)并将VA中每个结点的度匿名化为(din,dout)(8-11行)，匿名化后的结点标记为”anonymized”。当G中未匿名结点的数目小于2k-1时，迭代匿名化过程(2-13行)停止。此时，将标记为”unanonymized”和”postprocessing”的结点进行后期匿名(14行)。下面介绍算法具体细节。

3.2 匿名标签

在讨论RPA算法匿名化过程之前，首先介绍结点和边上的标签。边标签包括”added”和”un-added”。在图G中，标记”added”的边表示Gk中包含该边，”un-added”边表示Gk中无此边。结点标签”anonymized”表示已匿名结点，”unanonymized”表示未匿名结点，需要后期匿名的结点标记为”postprocessing”。当算法2基于Gd对G中结点和边的标签初始化时，结点均标记为”unanonymized”，在Gd中的边标记为”added”，其他边标记为”un-added”。

对于G中未匿名结点u，根据在Gk中的结点、边标签将u的出边分为三类：exist，non-exist和may-exist。图5中显示如何基于标签来确定u的出边类型。如图5(a)所示，标记为“added”的边属于exist类型，此类型边均存在于Gk。图5(b)中的边(u,v4)虽然标记了“un-added”，但是如果边(u,v4)存在于Gk中会使得v4不符合k-匿名，因此该边属于non-exist类型而不存在于Gk。图5(c)中的边(u,v5)和(u,v6)属于may-exist类型，即可能存在于Gk，因为将边(u,v5)和(u,v6)添加入Gk中不会对v5、v6是否符合k-匿名造成影响。相似地，可以给出G中的入边分类。

图5 基于在Gk中的结点、边标签将u的出边分为三类：exist，non-exist和may-exist

定义5.最小出度和最大出度. 已知图G(V,E)和结点u∈V，u的最小出度为u的exist出边数目，记作MIN_OUT(u)；u的最大出度为u的exist和may-exist出边数目之和，记作MAX_OUT(u)。

相似地，可以定义最小入度(记作MIN_IN)和最大入度(记作MAX_IN)。

3.3 结点匿名

算法2在匿名化结点u使其度为(din,dout)时(10行)，din和dout取值满足din≥MIN_IN(u)和dout≥MIN_OUT(u)。本节介绍如何匿名化结点的出度，入度匿名过程与之相似。

当MIN_OUT(u)≤dout≤MAX_OUT(u)时，算法2在u的may-exist出边中随机选择dout-MIN_OUT(u)条边并将其标签改为”added”；当dout>MAX_OUT(u)时，不仅将u的所有may-exist出边标记为”added”，还需添加dout-MAX_OUT(u)个伪结点，并添加边连接u至这些结点。由于新添加结点的度为(1, 0)或(0, 1)，根据社会网络幂率度分布可知，具有该度的结点数目远大于k，新结点符合k-匿名并标记为”anonymized”。如5.3节所示，匿名化真实社会网络时添加的假点数目很小，在保证匿名图安全性的同时不会对图数据可用性产生影响。在匿名化结点u后，将结点u标记为”anonymized”。

3.4 计算匿名化信息损失

将结点u的度匿名化为(din,dout)时，匿名信息损失计算公式为：

Cost(u,din,dout) =Costin(u,din) +Costout(u,dout)

其中，Costin(u,din)表示入度匿名信息损失，Costout(u,dout)表示出度匿名信息损失。入度匿名信息损失Costin(u,din)可计算为：

其中参数α是用于衡量边修改信息损失的权重参数，β是衡量d-可达性信息损失的权重参数。当MIN_IN(u)≤din≤MAX_IN(u)时，Costin(u,din)衡量了删边信息损失；当din>MAX_IN(u)时，Costin(u,din)计算了在添加结点和边后所增加的d-可达结点对导致的信息损失。可以看出，Costin(u,din)同时考虑了边修改信息损失和d-可达性信息损失。相似地，出度匿名信息损失Costout(u,dout)计算为：

3.5 选择种子结点和生成匿名结点集

已知图G(V,E)，算法2在选择种子结点Seed时，将具有最大MAX_IN(u)+MAX_OUT(u)的结点u作为Seed，然后选择k-1个与Seed具有最相似的度的结点来生成VA并进行匿名化。通过计算结点v和Seed在出、入度上的Manhattan距离来衡量两结点的度近似程度，距离越近表明两结点的度近似程度越高。

算法3. AnonymizationVertexSet.

输入：图G(V,E),种子结点Seed,匿名参数k、α和β

输出：匿名结点集VA

(1)din←MAX_IN(Seed),dout←MAX_OUT(Seed)；

(2)VA←φ；

(3)VertexList←V中合法的未匿名结点；

(4)基于Cost(v,din,dout) 升序排列VertexList中结点；

(5)repeat

(6)v←VertexList.head,将v从VertexList中删除；

(7) ifv与VA中其他结点无边连接 then

(8)VA←VA∪{v}；

(9) end if

(10)until |VA|=k或者VertexList=φ；

(11)returnVA.

已知种子结点Seed，算法3给出匿名结点集VA生成算法。在算法3中，合法结点u需要满足MIN_IN(u)≤din和MIN_OUT(u)≤dout。如果结点v与VA中其他结点具有边连接，则不加入VA(7行)，保证匿名化结点v不会影响VA中其他结点。给定种子结点Seed，需要检查O(n)个结点来生成VA，因此算法3的时间复杂度为O(n)。

为了获得最小匿名化信息损失，算法2基于VA计算最优度(din,dout)(8行)，其中din和dout的取值范围为：

最优度(din,dout)是指使得匿名VA中结点代价∑u∈VACost(u,din,dout最小化的入度和出度。

3.6 后期匿名处理

当算法2停止迭代匿名后，需要后期匿名化标记为”unanonymized”和”postprocessing”的结点(14行)：将剩余结点的MAX_IN最大值作为din，MAX_OUT最大值作为dout，并通过添加结点和边来匿名化这些结点的度。

当基于G中结点和边的标签来生成匿名图Gk时(15行)，首先将V(Gk)初始化为V(G)，然后将G中标记”added”的边添加进E(Gk)中。

4 实验结果与分析

本节对RPA算法进行性能分析和评价，采用社会网络数据集HepTh和Epinions进行测试(数据集可在http://snap.stanford.edu/data/下载)。表2给出了实验数据集的统计信息。除了实现本文的RPA算法，同时实现了文献[15]中的图匿名算法(记作Ngr-Degree)进行对比。在Ngr-Degree算法中，将边修改数目作为匿名信息损失度量的唯一标准，保证通过较少边修改数目来生成度匿名图。由于只考虑了边信息损失，因此理论上Ngr-Degree算法会导致更大的可达性信息损失。

表2 实验测试数据集统计信息

实验测试的软硬件环境为：(1)硬件环境：Intel Core 2 Duo 2.33 GHz CPU，4 GB DRAM 内存；(2)操作系统平台：Microsoft Windows XP；(3)编程环境：Java，Eclipse。本实验测试了图匿名化执行时间和匿名图数据可用性。RPA算法中权重参数默认设定为α=40和β=1。实验测试中距离阈值d在{2,4,6,|V|}中取值，当d=|V|时，希望匿名图保持原图中所有可达结点对间的可达性。

4.1 图匿名化执行时间

图6显示了图匿名执行时间随k值的变化情况。如图6所示，Ngr-Degree算法的执行时间少于RPA算法，这是因为Ngr-Degree没有考虑可达性信息损失，因此执行效率较高。当k增大时，RPA的执行时间降低，符合第5节中所分析的RPA算法时间复杂度。对于相同k值，d-RPA的执行时间随着d值的增大而增加。

图6 图匿名化执行时间

4.2 可达性信息损失

图7 当k=20时，Gk和G之间的可达性相似度

图8 Gk和G之间的4-可达性相似度随k值变化情况

4.3 结点和边信息损失

表3给出了当d=2、4、6时RPA生成匿名图中所添加的假点数目。当d保持不变时，随着k值的增大，假点数目增加；在相同的k值下，d值越大，假点数目越少。在匿名图中，假点只占图中结点很小的比例。以数据集HepTh为例，当k=5和d=4时，添加的假点数目为92，而匿名图中具有度(1, 0)和(0, 1)的结点数目为1268，远大于假点数目。

表3 匿名图中添加的假点数目

图9 边修改信息损失

5 结束语

本文针对图匿名技术对于结点间可达性的影响问题展开研究，提出了一种可达性保持图匿名化算法RPA。RPA算法基本思想是在图匿名化过程中保持最小d-RPG的完整性，从而实现结点间d-可达性的保持。基于真实数据集进行了大量实验测试和分析，验证RPA算法可以保证匿名图中结点间的可达性。

[1]Cheng J,Fu A,and Liu J.K-isomorphism:privacy preserving network publication against structural attacks[C].SIGMOD′10,2010:459-470.

[2]Gao J,Yu J,Jin R,et al.Neighborhood-privacy protected shortest distance computing in cloud [C].SIGMOD Conference,2011:409-420.

[3]Yuan M,Chen L,and Yu P S.Personalized privacy protection in social networks[C].VLDB′10,2010:141-150.

[4]Zou L,Chen L,and Ozsu M.K-automorphism:A general framework for privacy preserving network publication[C].VLDB′09,2009:946-957.

[5]Chen Y and Chen Y.An efficient algorithm for answering graph reachability queries[C].ICDE′08,2008:893-902.

[6]Jin R,Xiang Y,Ruan N,et al.Efficient answering reachability queries on very large directed graphs[C].SIGMOD′08,2008:595-608.

[7]Jin R,Liu L,Ding B and Wang H.Distance-constraint reachability computation in uncertain graphs[C].VLDB′11,2011:551-562.

[8]Nowell D L and Kleinberg J.The link prediction problem for social networks[C].CIKM′03,2003:556-559.

[9]Caragea D,Bahirwani V,Alj W,et al.Ontology-based link prediction in the livejournal social network[C].AAAI′09,2009.

[10]Liu X,Wang B and Yang X.Efficiently anonymizing social networks with reachability preservation[C].Proceedings of the 22th ACM Conference on Information and Knowledge Management (CIKM′13),2013:1613-1618.

[11]Liu K and Terzi E.Towards identity anonymization on graphs[C].SIGMOD′08,2008:93-106.

[12]Hazan E,Safra S,and Schwartz O.On the complexity of approximating k-dimensional matching[C].Approximation,Randomization,and Combinatorial Optimization Algorithms and Techniques,2003:59-70.

[13]Aho A,Garey M,and Ullman J.The transitive reduction of a directed graph[J].SIAM Journal on Computing,1972,1(2):131-137.

[14]Naddef,Denis.50 Years of integer programming 1958-2008[M].New York:Springer,2010:219-241.

[15]Zhou B and Pei J.Preserving privacy in social networks against neighborhood attacks[C].ICDE′08,2008:506-515.

(责任编辑：刘划 英文审校：刘飞)

On reachability preserving graph anonymization in social networks

LIU Xiang-yu,AN Yun-zhe,ZHOU Da-hai,XIA Xiu-feng

(College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

With increasing privacy concerns for social networks,graph anonymization has been extensively studied and numerous algorithms are proposed.The goal of graph anonymization is to avoid disclosure of privacy in social networks through graph modifications meanwhile to preserve data utility of the anonymized graph for social network analysis and graph queries.Reachability is an important data utility of the anonymized graph as reachability queries are not only common on graph databases,but they also serve as fundamental operations for many other graph queries.In practice,the reachability of vertices in the anonymized graph is nontrivially distorted.In this work,we solved the problem by designing a reachability preserving graph anonymization (RPA for short)algorithm.The main idea of RPA is to find a minimal subgraph that preserves the reachability of the vertices and keeps it unchanged during the anonymization.Extensive experiments on real datasets illustrate that anonymized social networks generated by our method can be used to answer reachability queries with high accuracy.

social networks;privacy;anonymization;reachability

2095-1248(2015)06-0050-09

2015-07-01

国家自然科学基金青年基金(项目编号：61502316)

刘向宇(1981-)，男，辽宁铁岭人，讲师，博士，主要研究方向：数据隐私保护，E-mail：neulxy@gmail.com。

TP301

A

10.3969/j.issn.2095-1248.2015.06.006