基于进化算法的社会网络数据k-匿名发布

胡　琪，蒋朝惠，吕晓丹

(贵州大学计算机科学与技术学院，贵州贵阳　550025)

基于进化算法的社会网络数据k-匿名发布

胡琪，蒋朝惠*，吕晓丹

(贵州大学计算机科学与技术学院，贵州贵阳550025)

基于科学发展的需要，越来越多的社会网络数据被共享发布。为保证发布数据中个体的隐私不被泄露，必须将数据进行隐私保护后发布。针对结点度的再识别攻击，提出一种改进的进化算法对社会网络发布的数据进行k-度匿名（CEAGA)，将EAGA算法中的适应度函数与循环结束条件进行改进，得到最优的k-度匿名序列，之后按照得到的k-度匿名序列对匿名图进行构造，得到最优的k-度匿名社会网络图。实验结果表明，改进后的进化算法不但降低了对原社会网络图的修改，并且对图结构性质的保持也优于EAGA算法。

社会网络；隐私保护；进化算法；k-度匿名；图结构性质

随着现代网络技术的快速发展，运输、医疗、社交、金融等的社会网络大量兴起，产生了许多非结构化的数据。为了科学研究的需要，科学家们希望将这些数据进行共享发布。如果将这些数据不加修改的随意发布出去，就会导致个人隐私的泄露。所以社会网络数据发布的隐私保护问题越来越成为研究者们研究的重点。社会网络数据和传统的关系型数据不同，社会网络数据由大量非结构化数据构成，一般用图的形式表示，所以对于传统关系型数据发布的研究不能直接运用到社会网络数据发布上。

社会网络的隐私保护策略主要取决于发布数据的效用，攻击者已获知的关于发布数据的一些信息，称之为攻击者的背景知识、隐私信息的类别等。国内外学者在已有关系型数据发布研究的基础上进行改进，提出了适用于社会网络数据发布的隐私保护方法。文献[1]针对匿名后发布数据的效用提出一种基于社区层次熵的k-匿名方法，较好的保持了图的性质，增加了匿名后数据的实用性。文献[2]对攻击者的背景知识为结点度的再识别攻击提出了k-度匿名。文献[3]对攻击者的背景知识为结点邻域信息的攻击提出了k-邻域匿名，并在文献[4]中进行改进使得匿名模型既满足k-匿名又满足l-多样性，使匿名模型对防止隐私泄露具有更高的安全性。文献[5][6]提出了一种k-同构匿名。文献[7]提出了一种泛化方法对社会网络图进行匿名。

可以看出在社会网络数据发布中k-匿名方法被广泛的运用。在k-匿名模型中，k-度匿名模型可以有效的抵御来自攻击者的背景知识为目标结点度的再识别攻击，如何有效的找到一组最优的k-度匿名序列来构造匿名图是 k-度匿名模型的关键。大部分研究都通过贪心算法得到k-度匿名序列，但贪心算法不从整体最优上加以考虑，总是做出在当前看来是最好的选择，得到的只是局部最优解。而文献[8]提出了一种基于进化算法的k-度匿名模型，利用进化算法来寻找全局最优的k-度序列。但只给出了基本的适应函数，该适应函数没有考虑图匿名后的实用性。本文在文献[8]的进化算法适应度函数中加入图密度的偏差比较，并对循环结束条件进行改进，实验结果表明改进后的算法较好的保持了匿名图的实用性。

1　相关概念

1.1社会网络图

社会网络中的数据一般以社会网络图形式表示。图中的结点代表社会网络中的各种实体如人，边表示实体之间的关系。一般社会网络图中的结点都带有属性值，同时还能对图中的边进行加权。例如在银行网络里所有实体都含有姓名、银行卡号等属性，实体A向实体B转账2000元钱，在社会网络图中，实体A与实体B有一条边相连，并且边的权重为2000。本文针对结点与边都不带有属性值的简单无向图进行研究。

定义1社会网络图G＝(V，E)。V为图G的节点集，表示社会网络图中的各种实体，E为图G的边集，代表实体与实体间的关系。

1.2k-度匿名

k-匿名是关系型数据发布运用范围最广的匿名模型之一。将关系数据的k-匿名模型进行改进，把社会网络图中结点度作为准标识符，称之为k-度匿名。对来自攻击者背景知识为目标结点度的攻击，k-度匿名对社会网络图G进行修改，使与目标结点度相同的其他结点数量不少于k-1个，即攻击者不能以高于1/k的概率识别出目标结点。

定义2有社会网络图G＝(V，E)，若图G中所有结点都是k-度匿名的，则称图G为k-度匿名图。

1.3进化算法

进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程与机制来寻找问题最优解的算法。在自然界中主要通过繁殖、变异、竞争和选择来实现生物进化；而进化算法则主要通过选择、重组和变异这三种操作实现优化问题的求解。在本文中主要通过选择、变异这两个操作来求得问题的解。算法主要框架如下:

族群P由一定数量的个体即问题的随机解组成，其中m表示变异算子，e表示评估算子，s表示选择算子。

2　基于改进进化算法的k-度匿名(CEAGA)

根据文献[2]所提出的方法，构造k-度匿名图主要有两个步骤:

(1)第一步，从原始社会网络图G中得到原始的度序列d＝{d1，……，dn}，之后根据公式(1)与隐私保护要求构造一个k-度序列之间的距离Δ最小。

2.1获取k-度匿名序列

对文献[8]提出的进化算法的适应度函数与循环结束条件进行改进，获取最优的k-度匿名序列，具体算法伪代码如下:

如Algorithm 1所示，文中用原始的度序列初始化族群P，之后得到族群中所有个体真实的'k'值。判断while循环结束条件，若不满足对族群进行变异处理，再对变异后族群中的个体进行评估。进化算法中对个体的评估主要依靠适应度函数，适应度函数根据一定的条件对每个个体进行打分，分数越高的个体越优秀。对于真实的'k'值不满足隐私保护要求(即k值)的个体，适应度函数从两个方面进行打分:

·个体中不满足k-匿名结点的数量，结点数量越多分数越低；

·结点的分散程度，计算个体中所有结点度到平均结点度之间的距离，距离越大分数越低；且对于真实'k'值不满足隐私保护要求的个体其分数应该位于[0，1]之间。

若个体真实'k'值满足隐私保护要求，为了保持最后得到社会网络匿名图的效用，我们在文献[8]的基础上加入图密度的测量，改进后的适应度函数从以下两个方面进行打分:

·计算个体度序列与原始度序列之间的距离，距离越远分数越低；

·计算个体密度与原始图密度之间的偏差，偏差越大分数越低；

并且满足隐私保护要求的个体分数应该在[1，2]之间。

对变异后族群进行评估之后，选择分数最高的个体加入族群中替换掉分数最低的个体，并获得个体真实的'k'值。对于while循环结束条件，我们将文献[8]中的while循环结束条件进行改进，增加一条循环结束条件，使得进化算法能够更加接近问题的最优解。改进后的while循环结束条件主要分为两个方面，个体真实的'k'值是否满足隐私保护需求，并且该个体在族群进行20次的变异选择后依然是最优的，若该个体同时满足两个条件，则循环结束，选择该个体的度序列作为最优的k-度匿名并输出。

2.2构造k-度匿名图

根据Algorithm 1得到的k-度匿名序列构造k-度匿名图，计算k-度匿名序列d～与原始度序列d之间的差异放入数组dcha中。

当差异值为正数时，需要在原社会网络图结点上加入边，为负数时则需要删除该结点的边，当差异值为0时，则不需要对该结点的边进行插入/删除操作。具体过程如下:

Algorithm 2构造k-度匿名图伪代码

在Algorithm 2中，若需要插入和删除边的结点数量不相等，则先将含有结点数多的集合进行插入/删除操作。如果Vadd>Vdel，则选择Vadd中的两个结点s，t，并且(s，t)∉E，在中插入边(s，t)，并在Vadd中删除节点s，t。结点若Vadd

3　实验结果及分析

3.1实验数据及参数设置

文中所用数据集Les Miserables[9]、Books about US politics下载于Krebs网站。数据集的具体信息如表1所示。实验环境采用Windows 7 Ultimate操作系统，CPU FX-6100 3.30 GHz，4.00 GB内存，编程语言为Java，运行平台为MyElipse10。

表1　数据集

对每个数据集，本文将与EAGA算法[8]进行比较，用边的交集来量度k-度匿名之后匿名图与原图的相似率。具体方法为

除此之外，用图的结构性质来进一步评价算法CEAGA和EAGA匿名后图的效用损失。图的结构性质主要包括聚类系数(CC)，平均路径长度(APL)。定义公式(4)来度量数据效用的改变率。P和P′分别代表原始图G和k-度匿名图的图结构性质，即CC、APL。

3.2实验结果

如图1所示，对于两个数据集，算法CEAGA 和EAGA对原图的改动都是比较小的，就算k值达到10时相似率也没有低于60%。如图1(a)所示，当k＝3时，经过算法EAGA后的匿名图与原数据集 Les Miserables的相似率为90%，经过改进算法CEAGA后的相似率为92%。如图1(b)所示，k＝10时，经过算法EAGA后的匿名图与原数据集Books about US politics的相似率为62%，而算法CEAGA为76%。可见改进后的算法CEAGA对原图进行边的插入/删除操作次数比算法EAGA少，进而对原图的改动也较小。

图1　边交集

如图2随着隐私保护要求的提高(即k值的增加)，数据效用损失在不断增加。因为k值越大，要使社会网络图中的所有结点达到隐私保护要求，就需要更多的对边进行修改，也就降低了图的实用性。实验用不同的图结构性质来评价图的效用损失，如图2(a)所示，对于数据集Les Miserables，当k＝5时，算法EAGA的聚类系数(CC)效用损失为29.6%，而改进算法CEAGA为26.3%，随着k值的增大，两者的效用损失逐渐接近，但总体上算法CEAGA的效用损失依然低于算法EAGA。如图2 (d)所示，对于数据集Books about US politics，k＝5时，算法EAGA的平均路径长度(APL)效用损失为14.1%，而算法 CEAGA只为 8.6%，低于算法EAGA。从实验结果中可以清楚地看到改进后的CEAGA算法能够有效的降低匿名后社会网络图的效用损失。

图2　图结构性质

4　总结

进化算法是一种运用非常广泛的寻找最优解的算法，但将进化算法运用到社会网络数据匿名发布中的研究还相对较少。本文在文献[8]的基础上对进化算法适应度函数与循环结束条件进行改进，使得匿名后的社会网络图进行科学研究时具有更高的效用。在今后的工作中将考虑用其他进化算法求得k-度匿名序列的最优解，并引入更多衡量图结构性质的指标，进一步提高匿名后社会网络图的实用性。

[1]WANG Y，XIE L，ZHENG B，et al.Utitily-Oritented k-anonymization on social network[C]//Proc of the 16th Int′l Conf On-Database Systems for Advanced Application，Hong Kong，China: DASFAA，2011:78-92.

[2]LIU K，TERZI E.Towards Identity Anonymization on Graphs[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data，Vancouver，Canada:ACM，2008:93-106.

[3]ZHOU B，PEI J.Preserving privacy in social networks against neighborhood attacks[C]//Proceedings of the 24th IEEE International Conference on Data Engineering(ICDE'08)，Cancun，Mexico: IEEE Computer Society，2008:506-515.

[4]ZHOU B，PEI J.The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks [J].Knowledge and Information System，2011，28(1):47-77.

[5]张伟，王旭然，王钰，等.基于k-邻域同构的动态社会网络隐私保护方法[J].南京电子科技大学学报，2014，34(5):9-16.

[6]ZOU L，CHEN L，OZSU M T.k-automorphism:a general framework for privacy preserving graph publication[C]//Proc of the VLDB Endowment，Lyon，France:ACM，2009:946-954.

[7]A Campan，T M Truta.Data and structural k-anonymity in social graphs[J].Lecture Notes in Computer Science，2008，5456:33-54. [8]Jordi Casas-Roma，Jordi Herrera-Joancomartí，Vicenä Torra.Evolutionary Algorithm for Graph Anonymization[DB/OL].(2014-03 -26).http://arxiv.org/pdf/1310.0229v2.pdf.

[9]D E Knuth.The Stanford GraphBase:A Platform for Combinatorial Computing[M].Boston:Addison-Wesley Professional，1993.

[10]CHENG J，FU A W，LIU J.K-isomorphism:Privacy Preserving Network Publication Against Structural Attacks[C]//Proceedings of the 2010 International Conference on Management of Data，Indianapolis，USA:ACM，2010:459-470.

[11]Panda G K，Mitra A，Prasad A，et al.Applying l-diversity in anony-mizing collaborative social network[J].International Journal of Computer Science and Information Security，2010，8 (2):324-329.

[12]兰丽辉，鞠时光，金华.社会网络数据的k-匿名发布[J].计算机科学，2011，38(11):156-160.

[13]BHAGAT S，CORMODE G，KRISHNAMURTHY B，et al.Privacy in dynamic social networks[C]//Proceeding of the 19th International Conference on World Wide Web，New York，USA:ACM，2010:1059-1060.

(责任编辑:周晓南)

Evolutionary Algorithm for Social Network Data Publication Based on k-anonymity

HU Qi，JIANG Chaohui*，LV Xiaodan
(College of Computer Science and Technology，Guizhou University，Guiyang 550025，China)

Based on the needs of scientific development，a growing number of social network data to be shared and released.In order to ensure that the privacy of the individual's privacy is not leaked，privacy protection should be carried on before releasing social networks data.For re-identification attack of the node degree，we proposed an improved evolutionary algorithm that to carry out the k-degree anonymity for social networks data.This paper improved fitness function and end condition of the loop of EAGA algorithm，and obtained optimal k-degree anonymous sequence.Then we obtained the optimal anonymous social network graph of k-degree by construct anonymous graph based on k-degree anonymous sequence that previous algorithms was generated.Experimental results show that the improved evolutionary algorithm not only reduces the modification of the original social network graph，keep the property of the graph structure is better than EAGA algorithms.

social network；privacy protection；evolutionary algorithm；k-degree anonymous；property of the graph structure

TP393.08

A

1000-5269(2016)01-0089-05DOI:10.15958/j.cnki.gdxbzrb.2016.01.21

2015-10-30

贵州省基础研究重大项目资助(黔科合JZ字[2014]2001)

胡琪(1991-)，女，在读硕士，研究方向:网络与信息安全，Email:huqi19910808＠163.com.

蒋朝惠，Email:jiangchaohui＠126.com.