基于k-度匿名的社会网络隐私保护方法

龚卫华，兰雪锋，裴小兵，杨良怀

(1.浙江工业大学计算机科学与技术学院，浙江杭州 310023； 2.华中科技大学软件学院，湖北武汉 430074)



基于k-度匿名的社会网络隐私保护方法

龚卫华1，兰雪锋1，裴小兵2，杨良怀1

(1.浙江工业大学计算机科学与技术学院，浙江杭州 310023； 2.华中科技大学软件学院，湖北武汉 430074)

针对当前社会网络的匿名化隐私保护方法存在信息损失量巨大、网络关系结构被改变严重等问题，提出一种保持网络结构稳定的k-度匿名隐私保护模型SimilarGraph，运用动态规划方法对社会网络按照节点度序列进行最优簇划分，然后采用移动边操作方式重构网络图以实现图的k-度匿名化.区别于传统的数值扰乱或图修改如随机增加、删除节点或边等方法，该模型的优势在于既不增加网络边数和节点数，也不破坏网络原有连通性和关系结构.实验结果表明，SimilarGraph匿名化方法不仅能有效提高网络抵御度属性攻击的能力，并且还能保持网络结构稳定，同时具有较理想的信息损失代价.

社会网络；隐私保护；k-度匿名；信息损失

1　引言

近年来，社会网络的流行已深刻地改变了人们的日常生活和交流方式，国内外著名社交网站如Facebook、QQ、人人网等注册用户数量不断攀升，以Facebook为例，用户总数在2013年已突破10亿，其中包含1500亿条朋友链接，这些社会网络数据蕴含巨大的商业价值和应用前景，例如可促进广告、游戏、零售等业务迅速增长.然而，人们在使用基于社会网络的应用同时面临着严重的隐私信息泄露和恶意攻击问题.因此，研究社会网络的隐私保护技术显得尤为重要.

社会网络属于复杂网络的研究范畴，关注的是社会个体及个体间的互动和联系，同样具有“小世界”现象和幂律分布特征[1～3]，但这使得社会网络所包含的2类重要隐私信息(节点属性数据和关系数据)极易遭受节点度攻击、链接攻击等结构化攻击.目前针对社会网络的隐私保护问题已取得一些研究成果，如从节点属性数据角度出发的隐私保护类似于数据发布研究中的隐私保护方法[4～6]，侧重保护标识或敏感属性如姓名、电话、地址等，常采用已比较成熟的数据泛化[7～10]、扰动[5,11]或添加噪声节点[12]等方法.而针对关系数据的隐私保护则是亟待人们深入探索的研究热点，通常被建模为图数据并采用数值扰乱法或图修改法如随机增加、删除节点或边[13]，以及修改边权重值[14]来实现隐私保护.总体上看，现有的社会网络隐私保护方法大多基于如何实现各种匿名化模型如节点k-匿名、子图k-匿名等[15]，但他们都面临由于匿名化而带来巨大的信息损失问题，甚至还会严重破坏社会网络关系结构，显著降低了网络数据的效用.

本文针对社会网络中关系数据这类隐私对象提出一种改进的基于图的k-度匿名模型SimilarGraph，该模型首先运用动态规划思想进行基于节点度的最优簇划分，然后，通过移动边方式重构网络图实现图的k-度匿名化.该方法不仅能克服传统匿名化算法所存在严重的信息损失缺点，还有效保持了社会网络原有连通性和内在关系结构稳定，并提高了抵御度属性攻击的能力.

2　相关工作

目前，现有针对网络关系数据的隐私保护研究大多数都采用匿名化模型来防止隐私信息泄露和恶意攻击，其主要途径有基于聚类方法和图修改方法.

基于聚类的匿名化方法是先对节点、边或两者同时聚类成簇，然后通过泛化方式来达到匿名化效果.文献[16]提出将网络中相似节点聚合为一簇，每个簇所包含的节点数≥k，这样使得攻击命中率降为1/k.Campan等[8]采用贪心策略对网络中属性相似的节点进行聚类并使用边泛化方法实现k匿名的网络，该方法考虑了匿名化过程中的信息损失问题.文献[17]对加权无向网络采用节点聚类和边聚类相结合的泛化方式实现k-匿名模型，但缺点是严重改变了网络结构，同时还降低了匿名化后的网络数据效用.

近年来，采用图修改方法实现网络匿名化已成为国内外研究者关注的热点，Liu等[18]提出图的k-度匿名概念，即要求图中任一顶点都至少有k-1个顶点与其度数相同，并运用贪心策略采用增加边的方式来实现匿名图，以抵御节点度属性攻击，该方法虽然考虑了图修改的最小代价问题，但破坏了网络连通性使得网络内在关系结构发生重大变化.Yuan[19]和Zhou[20]都针对具有节点属性标签的社会网络提出了k-度-l多样化匿名模型，该模型在k度匿名的基础上要求相同度数的k个节点必须有l种不同标签，并通过增删边和添加噪声节点的方法实现属性匿名，但他们都没有考虑匿名化所造成的信息损失影响.Zheleva等[21]将关系边区分为敏感边和非敏感边并提出通过删除敏感边的方式实现图的匿名化，以防止链接再识别攻击，其不足之处在于数据匿名化的效用由删除边的数量多少决定，缺乏对信息损失量的考虑，严重破坏原有网络的连通性.此外，Zou等[22]运用图同构理论提出k-同构匿名模型防御结构化攻击，要求网络任一子图至少有k-1个与其同构的子图，其缺点是同构图的匹配和重构造代价较大，特别是图转化时需要复制边的操作破坏了原有网络的结构特性.

综上所述，基于聚类的匿名模型由于泛化后存在严重的信息损失问题，导致网络结构发生巨大变化，数据效用急剧降低.而针对图数据修改或转化的匿名化方法大多都采用添加、删除节点或边以及子图同构等扰动方式实现k-度匿名，但这种图随机修改策略忽略了社会网络内在结构特性，仍无法克服较大的信息损失问题.为此，本文提出的隐私保护模型SimilarGraph与传统的数值扰乱或图修改方法不同之处在于采用移边方式替代随机增、删节点或边等操作，并能在网络节点数和边数都保持不变条件下以最小的信息损失代价移动关系边实现网络的k-度匿名化，因而既不损害社会网络原有连通性和关系结构，还有效提高了抵御度属性攻击的能力.

3　相关定义

为了便于研究，本文将社会网络建模为无权无向图G=(V,E)，其中V表示为社会网络中的节点集，E表示节点间的关系边集，且E⊆V×V.一般情况下，图中节点及其关系极易受到节点度攻击、链接攻击等结构化攻击，因此，实现图中节点及关系边的匿名化是一种重要的隐私保护方法，下面先给出一些基本定义.

图的k-度匿名借鉴了传统数据表中的k-匿名思想[11]，使得图中节点间关系及其度分布趋于同构，这将有效降低结构化攻击的概率，至少小于等于1/k.从另一角度看，社会网络可看成由若干子图构成，每个子图都满足k-度匿名模型，这样得出网络的k-度匿名概念.

由定义2可知，社会网络被划分成满足k-度匿名的各簇实际上可称为匿名簇，同一簇内的节点都具有相同的度属性，而不同的匿名簇间满足不同的k-度匿名要求.对于相同簇中的节点由于具有同构特征而不易受攻击，并且如果簇越大、簇数量越多，其遭受攻击的难度也越大.因此，当社会网络被划分成满足定义2的m个簇时，受到恶意攻击的概率将进一步下降到1/(m·k).

为了便于社会网络按照节点度特征划分成各匿名簇，下面给出基于递减度的序列结构.

定义3递减度的节点序列Sq(〈v1…vi〉)：如果网络图G的节点集V={v1,…,vi}中所有节点按照递减度的偏序关系排列，即满足Dg(v1)≥…≥Dg(vi)，则该递减度节点序列表示为Sq(〈v1…vi〉).

根据定义3，如果节点序列Sq(〈v1…vi〉)中所有节点的度数都相等，并且序列的节点数|Sq|≥k，则该序列Sq可看作一个符合k-匿名要求的簇序列.

(1)

定义4中，簇的信息损失量衡量了单个匿名簇内节点度变化对网络原有结构造成的影响程度.在此基础上，可进一步通过累加所有匿名簇的信息损失量获得整个社会网络匿名化的信息损失代价，即原始网络G与匿名网络G′间的节点度变化量为：

(2)

定义5信息损失率(R)：满足k-度匿名的社会网络G′的信息损失量与其原始网络G中总度数的比值称为信息损失率：

(3)

式(3)中，I(G′/G)表示整个社会网络匿名化的信息损失量，由式(2)计算；而对于原始网络G的节点总度数，由图的握手定理可得：当网络G的边数为|E|时，其总度数和为2|E|.

4　图的k-度匿名隐私保护方法

针对建模成图结构的社会网络，本文提出基于移边操作的k-度匿名隐私保护方法，基本思路是将整个匿名化过程分为两个步骤：(1)基于度的最优簇划分；(2)移边操作重构网络图实现k-度匿名化.

4.1基于度的最优簇划分

最优簇划分是以信息损失量最小化代价为目标对网络节点进行簇划分，并确定簇内每个节点满足k-度匿名的度数.为了实现该目标，本文先将社会网络G=(V,E)中节点集V按照定义3排序成递减度序列形式：

然后基于节点度划分成m个匿名簇，并使其满足定义2中的k-度匿名要求，这样匿名簇的度序列转变为如下结构：

Sq′(〈v11v12…v1t1,v21v22…v2t2,vm1vm2…vmtm〉)

=〈vi1vi2…viti〉,

可以看出，对整个社会网络节点的簇划分等价于递减度序列的簇划分,并且要求信息损失量最少.我们采用动态规划方法对递减度序列结构Sq进行簇划分，动态规划特别适合具有重叠子过程的多阶段决策问题，要求出一个过程的最优解必须求出其子过程的最优解，这样逐步递推直到求出整个过程的最优解.因此，本文提出最优簇划分的代价函数如式(4)所示.

(4)

约束为

(5)

算法1最优簇划分算法

输入：网络图G中的节点递减度序列Sq(v1,v2,…,vn)，匿名k度值.

输出：最优匿名簇Sq′的划分序列号t1,…,tm.

1.ifn<2kthen

2.return簇序列Sq′(v1,v2,…,vn);

3.else//对于n≥2k情况

4.fori=n-k+1 tokdo

5.ifi>n-2k+1 then//当n-2k+1

6.form=itondo

8.endfor

9.elseifi>kthen //当k

10.由式(1)计算I(〈vi…vn〉);

11.endif

12.endfor

13.fort=kton-kdo

14.由式(1)计算I(〈v1…vt〉);

16.endfor

18.return最优簇序列Sq′的划分序号[t1,…,ti]；

19.endif

4.2网络图重构算法

经过最优簇序列划分后，网络图中每个节点将获得实现k-度匿名化所属簇的平均度数.本文采用移边方式实现匿名化操作，即将高于簇平均度的节点上的边移动到低于簇平均度的节点上.实际上，移边操作可等价于先删除边再增加边这两步原子操作，成功的移边操作应使其两端节点都同时满足度匿名的变化方向.

(6)

对于网络中的任意边来说，其两端节点vi和vj的函数γ状态共同决定了该边是否符合增删操作要求，如图1所示6种状态，除了图1(f)中边上两端节点都已满足匿名化要求外，剩余5种情况图1(a)～(e)都需要通过增删边来改变节点度数.不难得知，由于图1(b)、(c)和(e)都至少有一端存在度关系“<”，因而不满足移边操作中需先删除边的前提条件，而只有图1(a)和(d)满足该前提条件，且节点度符合匿名变化方向.

为了保持图结构的连通性，移边操作中的删除边与增加边间存在必要的关联条件是这两条边的端点在图中体现互为连通邻居.具体地，针对图1(a)和图1(d)的移边方法分别对应图2(a)和图2(b)，图中移边的先后步骤等于①删除边+②增加边(虚线表示).图2(a)中新增边的两节点vp和vq分别是被删边上节点vi和vj的连通邻居，并且都有增加节点度要求.而图2(b)中为了维持被删边上的节点vj度不变的要求，新增边的一端必须从vj出发，而另一端则是vi中需增加节点度的连通邻居.

为了实现基于移边的网络图匿名化，本文给出满足k-度匿名的重构网络图算法2，算法中假设已知原始图中各节点vi的度数Dg(vi).

算法2重构网络图算法

输出：重构后的k-度匿名网络图G′

1.for each edge(vi,vj)∈Edo

3.forvp∈N(vi的连通分量) do

5.forvq∈N(vj的连通分量) do

7.{删除edge(vi,vj)后两端节点度-1;

8.增加edge(vp,vq)后两端节点度+1;}

9.endif

10.endfor

11.endif

12.endfor

14.forvp∈N(vi的连通分量) do

16.{删除edge(vi,vj)后节点Dg(vi)-1;

17.增加edge(vp,vj)后节点Dg(vp)+1;}

18.endif

19.endfor

20.endif

21.endfor

22.return重构后的网络G′

5　仿真实验及结果分析

本文采用CA-GrQc数据集构建社会网络进行实验与分析，该数据集包括5242个节点，14496条无向边，度分布服从幂律分布.为了便于实验比较和说明，我们将第4节所提出的社会网络基于图的k-度匿名隐私保护方法称为SimilarGraph模型，算法代码用Python编程实现，实验环境为Intel(R) CoreTMi5 CPU 2.3GHz，4GB内存，操作系统为Windows7.实验方法是先由算法1对原始网络数据集进行最优的k-度匿名簇划分，再用算法2进行移边操作来重构匿名化的网络图，然后采用Gephi工具对其可视化并对比网络匿名化前后节点度变化及分布特征.

图3(a)展示了原始社会网络的节点度分布图，节点度数越多则呈现越大，图中共标注了8种度区间的节点分布情况.图3(b)则显示当k=50时匿名化网络的分布图，其度特征明显下降，节点共被划分成21个簇，与图3(a)对比后发现，原始社会网络中节点度大于70的显著节点只有4个，对其成功攻击的概率有1/4，而在匿名后的图3(b)中，至少有50个以上节点与其相似，这样攻击概率便降至1/50以下.

图4显示了不同匿名k值下社会网络度的幂律分布规律，图中k=0时表示原始社会网络的度服从幂律分布，其度数介于10到80之间的节点分布不均匀且同构节点数偏少，度数大的节点最容易遭受攻击，而实现不同k-度匿名化后的网络度分布虽然也满足幂律特征，但其结构趋于均匀，最大节点度数随着匿名k值增大而逐渐减少，节点聚集特性也越明显，特别是当k值越大时匿名网络中节点度大于10以上的同构节点数越多，这样大大增加了针对网络度属性攻击的难度.

下面，将本文提出的模型SimilarGraph与经典的k-度匿名方法SuperGraph[18]和最近Yuan等[19]提出的模型KDLD进行各项实验指标对比，三者区别在于SimilarGraph采用移边方法而SuperGraph则采用随机增加边方式实现网络匿名化，对于KDLD则是通过增加噪声节点来实现k-度匿名化.图5比较了三种方法在实现不同k-度匿名化网络过程中发生边移动、增加或因噪声节点而增加边的变化数量，当匿名k值增大时，SimilarGraph实现匿名化所需移动的边数增长较小且比较平稳，而SuperGraph所需改变的边数从222增加到2675条，KDLD也与其较一致，增长幅度都很显著.总体上看，SimilarGraph的边变化数远小于SuperGraph和KDLD.

图6进一步统计了三种方法实现匿名化后带来的信息损失率结果，该指标由式(3)计算.图6中SimilarGraph在实现不同k值匿名化网络时由移边操作所引起的信息损失率非常小，而SuperGraph和KDLD两者都增加了大量边而造成较大的信息损失率且增长趋势较明显，由此可见，SimilarGraph方法具有最理想的移边代价.

另外，为了对比网络匿名化前后的结构特性变化，图7、图8和图9分别给出了三种方法在不同k-度匿名化网络中的聚类系数(CC)、节点平均度和平均路径长度(APL)等指标结果，图中用虚线表示了原始网络的相关指标值，它不随匿名k值而变化.由图7可知，KDLD方法当k在50～70区间时由于增加了一些噪声节点以及需增加、删除相关边，导致其CC指标出现较明显的先升后降趋势，整体网络结构变化较大，表现不稳定，而SuperGraph方法随k值增大而所增边数越多造成CC指标逐渐下降.总体上看，本文的SimilarGraph方法在不同k值下一直最接近于原始网络的聚类系数值，对匿名化后的网络结构影响最小.

图8中当匿名k值增大时，SimilarGraph产生的匿名化网络中节点平均度数与原始网络基本相同，而KDLD方法使得不同k值匿名化的网络节点平均度逐渐下降，对网络结构影响较小，SuperGraph则使匿名后的节点平均度增幅较大，表明该匿名方法比较严重地破坏了原始网络结构.

图9比较了网络匿名化前后的平均路径长度(APL)指标，三者之中本文的SimilarGraph表现最好，该方法使得匿名化的网络APL在不同k值下都保持较小幅的下降且比较平稳，而KDLD在匿名化后由于增加了一些噪声节点导致APL指标有小幅度上升，SuperGraph则采用随机增加边方式引起匿名化网络的APL指标有较大的下降.由此表明，SimilarGraph能保持比较稳定的网络内在关系结构.

最后，由于本文实验所选取的数据集CA-GrQc中节点无属性标签，因此，KDLD模型无法在相同条件下与SimilarGraph和SuperGraph比较抗恶意攻击能力，图10和图11分别对比了SimilarGraph和SuperGraph两种方法在不同k-度匿名值下的网络划分簇数量和遭受度攻击的平均概率.从图10统计的匿名簇数量对比来看，当匿名k值增大时，SimilarGraph和SuperGraph两者在实现匿名化网络时所划分的簇数量都是逐渐减少且大致接近.另一方面，图11中的平均攻击概率等于对所有簇节点攻击的概率平均值，概率值越小表示匿名化网络抵御节点度攻击的能力越强，由图11结果可知，两种方法都使得匿名化网络遭受度攻击的概率大大减小，而SimilarGraph抵御恶意攻击的能力总体上优于SuperGraph.

6　总结

现有社会网络的隐私保护方法普遍存在比较严重的信息损失，以及匿名化后网络结构特征发生巨大改变的问题.针对这些不足，本文提出一种保护社会网络关系数据的k-度匿名模型SimilarGraph，该模型先从网络节点度序列出发运用动态规划方法进行最优簇划分，然后，采用移动边方式对网络进行扰动，并进一步重构网络实现基于图的k-度匿名化的隐私保护.最后，采用CA-GrQc数据集构建社会网络进行实验与分析，各项实验结果表明SimilarGraph方法能在网络节点数和边数都保持不变条件下以最小的信息损失代价移动关系边实现网络的k-度匿名化，克服了传统匿名化算法存在严重的信息损失缺点，而且还有效保持了社会网络结构和内在联系的稳定，同时提高了网络抵御度属性攻击的能力.限于篇幅，我们下一步研究工作是改进本文所提出的匿名化模型实现并行化以求改变全局优化过程计算复杂的局面，并考虑在更大的实际网络数据集上进行实验验证其有效性.

[1]Boccaletti S,Latora V,Moreno Y,et al.Complex networks:structure and dynamics[J].Physics Reports,2006,424(4):175-308.

[2]Wang X F,Chen G R.Complex networks:small-world,scale-free and beyond[J].IEEE Circuits and Systems Magazine,2003,3(1):6-20.

[3]Faloutsos M,Faloutsos P,Faloutos C.On power-law relationships of the internet topology[A].ACM SIGCOMM'99[C].Cambridge,Massachusetts:ACM,1999.251-262.

[4]童云海,陶有东,唐世渭,等.隐私保护数据发布中身份保持的匿名方法[J].软件学报,2010,21(4):771-781.Tong Yun-hai,Tao You-dong,Tang Shi-wei,et al.Identity-reserved anonymity in privacy preserving data publishing[J].Journal of Software,2010,21(4):771-781.(in Chinese)

[5]黄茂峰,倪巍伟,王佳俊,等.一种面向聚类的对数螺线数据扰动方法[J].计算机学报,2012,35(11):2275-2282.

Huang Mao-feng,Ni Wei-wei,Wang Jia-jun,et al.A logarithmic spiral based data perturbation method for clustering[J].Chinese Journal of Computers.2012,35(11):2275-2282.(in Chinese)

[6]张啸剑,孟小峰.面向数据发布和分析的差分隐私保护[J].计算机学报,2014,37(4):927-949.

Zhang Xiao-jian,Meng Xiao-feng.Differential privacy in data publication and analysis[J].Chinese Journal of Computers,2014,37(4):927-949.(in Chinese)

[7]Campan A,Truta T M,Cooper N.P-sensitive K-anonymity with generalization constraints[J].Transactions on Data Privacy,2010,3(2):65-89.

[8]Campan A,Truta TM.A clustering approach for data and structural anonymity in social networks[A].2nd ACM SIGKDD International Workshop on Privacy,Security,and Trust in KDD(PinKDD'08)[C].Las Vegas,NV:ACM,2008.33-54.

[9]王智慧,许俭,汪卫,等.一种基于聚类的数据匿名方法[J].软件学报,2010,21(4):680-693.

Wang Zhi-hui,Xu Jian,Wang Wei,et al.Clustering-Based approach for data anonymization[J].Journal of Software,2010,21(4):680-693.(in Chinese)

[10]张健沛,谢静,杨静,等.基于敏感属性值语义桶分组的t-closeness隐私模型[J].计算机研究与发展,2014,51(1):126-137.

Zhang Jianpei,Xie Jing,Yang Jing,et al.At-closeness privacy model based on sensitive attribute values semantics bucketization[J].Journal of Computer Research and Development,2014,51(1):126-137.(in Chinese)

[11]付艳艳,张敏,冯登国,等.基于节点分割的社交网络属性隐私保护[J].软件学报,2014,25(4):768-780.

Fu Yan-yan,Zhang Min,Feng Deng-guo,et al.Attribute privacy preservation in social networks based on node anatomy[J].Journal of Software,2014,25(4):768-780.(in Chinese)

[12]Wu W T,Xiao Y H,Wang W,et al.k-symmetry model for identity anonymization in social networks[A].13th International Conference on Extending Database Technology(EDBT’10)[C].Lausanne,Switzerland:ACM,2010.111-122.

[13]Ying X,Wu X.On link privacy in randomizing social networks[J].Knowledge and Information Systems,2011,28(3):645-663.

[14]刘华玲,郑建国,孙辞海.基于贪心扰动的社交网络隐私保护研究[J].电子学报,2013,41(8):1586-1591.Liu Hua-ling,Zheng Jian-guo,Sun Ci-hai.Privacy preserving in social networks based on greedy perturbation[J].Acta Electronica Sinica,2013,41(8):1586-1591.(in Chinese)

[15]刘向宇,王斌,杨晓春.社会网络数据发布隐私保护技术综述[J].软件学报,2014,25(3):576-590.

Liu Xiang-yu,Wang Bin,Yang Xiao-chun.Survey on privacy preserving techniques for publishing social network data[J].Journal of Software,2014,25(3):576-590.(in Chinese)

[16]Hay M,Miklau G,Jensen D,et al.Resisting structural re-identification in anonymized social networks[J].The VLDB Journal,2010,19(6):797-823.

[17]Skarkala M E,Maragoudakis M,Gritzalis S,et al.Privacy preservation by k-anonymization of weighted social networks[A].Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining(ASONAM)[C].Istanbul,Turkey:IEEE Computer Society,2012.423-428.

[18]Liu K,Terzi E.Towards identity anonymization on graphs[A].2008 ACM SIGMOD International Conference on Management of Data(SIGMOD’08)[C].New York:ACM,2008.93-106.

[19]Yuan M X,Chen L,Yu P S,et al.Protecting sensitive labels in social network data anonymization[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(3):633-647.

[20]Zhou B,Pei J.The K-anonymity and L-diversity approaches for privacy preservation in social networks against neighborhood attacks[J].Knowledge and Information Systems,2011,28(1):47-77.

[21]Zheleva E,Getoor L.Preserving the privacy of sensitive relationships in graph data[A].1st ACM SIGKDD Workshop on Privacy,Security,and Trust in KDD (PinKDD'07)[C].San Jose,CA:ACM,2007.153-171.

[22]Zou L,Chen L,Özsu M T.K-automorphism:a general framework for privacy preserving network publication[J].Proceedings of the VLDB Endowment,2009,2(1):946-957.

龚卫华男，1977年生于湖北武汉，博士，现为浙江工业大学计算机学院副教授.主要研究方向：数据挖掘、社会网络、大数据计算等.

E-mail:whgong@sohu.com

兰雪锋男，1990年生于浙江丽水，浙江工业大学硕士生.主要研究方向：社会网络、隐私保护.

裴小兵男，1971年生于湖北，博士，现为华中科技大学软件学院副教授.主要研究方向：机器学习、数据挖掘、软件工程、电信网络管理.

E-mail:xiaobingp@hust.edu.cn

杨良怀男，1967年生于浙江新昌，博士，现为浙江工业大学计算机学院教授，主要研究方向：数据库系统、数据挖掘、大数据计算等.

E-mail:yanglh@zjut.edu.cn

Privacy Preservation Method Based on k-Degree Anonymity in Social Networks

GONG Wei-hua1,LAN Xue-feng1,PEI Xiao-bing2,YANG Liang-huai1

(1.SchoolofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou，Zhejiang310023,China;2.SchoolofSoftwareEngineering,HuazhongUniversityofScienceandTechnology,Wuhan，Hubei430074,China)

To preserve the privacy of social networks,most existing methods are applied to satisfy different anonymity models,but some serious problems are involved such as often incurring large information losses and great structural modifications of original social network after being anonymized.Therefore,an improved privacy protection model called SimilarGraph is proposed,which is based onk-degree anonymous graph derived fromk-anonymity to keep the network structure stable.Where the main idea of this model is firstly to partition network nodes into optimal number of clusters according to degree sequences based on dynamic programming,and then to reconstruct the network by means of moving edges to achievek-degree anonymity with internal relations of nodes considered.To differentiate from traditional data disturbing or graph modifying method used by adding and deleting nodes or edges randomly,the superiority of our proposed scheme lies in which neither increases the number of nodes and edges in network,nor breaks the connectivity and relational structures of original network.Experimental results show that our SimilarGraph model can not only effectively improve the defense capability against malicious attacks based on node degrees,but also maintain stability of network structure.In addition,the cost of information losses due to anonymity is minimized ideally.

social network；privacy preservation；k-degree anonymity；information loss

2015-01-25；修回日期：2015-10-23；责任编辑：梅志强

浙江省自然科学基金(No.LY13F020026,No.Y1080102,No.LY14F020017,No.LY14C130005)；国家自然科学基金(No.61571400,No.61070042)；中国博士后科学基金(No.2015M581957)；浙江省博士后科研项目择优资助(No.BSH1502019)

TP309.2

A

0372-2112 (2016)06-1437-08