基于敏感关系的社会网络隐私保护方法

申艳光，闫晶星＋，买建英，范永健

（1.河北工程大学 信息与电气工程学院，河北 邯郸056038；2.解放军炮兵训练基地，河北 宣化075100）

0 引 言

用户隐私信息的非法出售、假冒身份欺诈、社会网站本身存在的漏洞及第三方应用程序的植入等对用户的个人隐私造成了严重的威胁。由于社会网络的复杂性，攻击者可能具有大量的背影知识，同时抵御多种类型攻击的隐私保护成为研究热点。

目前，社会网络中节点间的连接关系可能导致的隐私泄露问题［1，2］受到了人们的广泛关注。Gao等［3］将两结点之间的边连接视为隐私信息，保证在不得知结点之间边连接情况的同时准确地计算任意两点之间的最短路径长度。针对节点连接关系和社会网络图结构可能造成的隐私信息泄露问题，杨俊等［4］提出了一种基于图自同构的k－Secure社会网络隐私保护模型，从而有效防止节点识别、边识别和路径长度泄露等隐私攻击。已有的社会网络隐私保护大部分只针对单一关系的社会网络，由于社会网络的特殊性，多关系的社会网络中多数据类型的隐私保护同样受到人们的重视。Zhelea等［5］针对单类型节点多类型边进行了匿名化处理。（k，2）－匿名模型［6］、l－敏感边匿名模型［7］等都对节点间的敏感关系进行了隐私保护。Zheleva等［8］通过现有边连接间的敏感关系计算节点间具有敏感关系的概率，实现对被删除敏感边的恢复。Campan等［9］提出了p－敏感k－匿名模型。南丽丽等［10］提出了一种基于信息混淆的社会网络隐私保护机制。王小号等［11］针对攻击者以社会个体领域信息作为背景知识进行敏感边识别的攻击，提出了基于谱约束的敏感区划分随机扰动方法。张健沛等［12］针对等价类与数据表间敏感属性分布的稳定性，提出了一种SABuk tcloseness模型。吴宏伟等［13］提出了一种抗复合攻击的 （k，l）－匿名发布算法，有效解决了抵御复合攻击的问题。但是，以上匿名方法并没有考虑抵御社会网络中存在的节点间敏感关系和社会网络图结构造成的隐私信息泄露问题。

本文针对社会网络中敏感边攻击、节点度攻击和朋友连接攻击同时存在的问题，提出了一种面向含敏感关系的（k2，l）－匿名模型。

1 面向含敏感关系的 （k2，l）－匿名模型

为了便于研究，社会网络通常被抽象为图结构，利用较为成熟的图论知识对社会网络进行研究。实际生活中存在多种不同类型的复杂的社会网络，本文针对含敏感关系的社会网络进行研究。含敏感关系的社会网络图定义如下：

定义1 含敏感关系的社会网络：社会网络图G＝（V，E，T）。其中，V 表示节点，E 表示节点间的关系，T表示边的类型，若T 为1，则表示E 为敏感关系；T 为0，则表示E非敏感关系。

社会网络中含敏感边，首先通过添加非敏感边构建l－敏感边匿名模型，然后通过添加非敏感边实现 （k2，l）－匿名模型。

定义2 l－敏感边匿名模型：给定一个图G＝ （V，E，T），若节点v有敏感关系，至少存在l个节点与节点v 有敏感关系，那么该图满足l－敏感边匿名模型。

定义3 （k2，l）－匿名模型：给定一个图G＝（V，E，T），对图中任意具有度对为d2＝ （d1，d2）事件边的节点v，至少存在k－1个其它节点和v具有一个相同度对的事件边；且若节点v有敏感关系，则至少存在l个其它节点与节点v有敏感关系。那么该图满足（k2，l）－匿名模型。

分别通过添加敏感边和非敏感边构建匿名模型，社会网络图的可用性会降低，本文通过节点的度衡量社会网络图的匿名损失，社会网络图匿名信息损失量定义如下：

定义4 匿名度信息损失量：匿名图G＊与原始图G 总的度差称为匿名度信息损失量，定义为式 （1）

式 中：d（G＊）（i）—— （k2，l）－匿 名 图 节 点i 的 度，G＊—— （k2，l）－匿名图；d（G’）（i）——l－敏感边匿名图节点i的度，G’——l－敏感边匿名图；n——图中的节点数。

2 面向含敏感关系的 （k2，l）－匿名化方法

本节首先介绍含敏感关系的 （k2，l）－匿名化方法，然后介绍具体的实现算法。

2.1 面向含敏感关系的 （k2，l）－匿名化

根据 （k2，l）－匿名化要求。首先，对网络中的节点添加敏感边，使每个含敏感关系的节点至少与l个节点相连。然后，在满足l－敏感边匿名模型的基础上，提出了基于动态规划的度序列匿名算法 （dynamic programming degree sequence anonymization，DPDSA）和基于贪心算法的度序列匿名算法 （greedy algorithm degree sequence anonymization，GADSA），构建 （k2，l）－匿名模型。度序列匿名算法的基本思想如图1所示。

图1 度序列匿名算法基本思想

为了降低匿名成本，在添加敏感边的过程中首先选择与不满足l－敏感边匿名模型且含有敏感关系的节点相连，其中l的值根据用户所需的隐私保护程度而定。在添加非敏感边时选择的节点应遵循以下3个准则：

（1）一个节点没有和另一个组中的任何节点相连；

（2）两个节点分别在各自组中度最小；

（3）在两组节点中两点之间路径最短的节点。

2.2 算法实现

本节介绍具体的 （k2，l）－匿名模型实现算法，分为3个主要模块进行介绍：动态规划分组算法、贪心算法分组算法和构建 （k2，l）－匿名模型算法。

2.2.1 动态规划求分组节点算法

提取每个节点的度，按节点的度降序排列。采用动态规划的分组策略根据度的相似性进行分组，每个组至少包含k个节点并将每个组中节点最大的度作为本组的目标度dx。

算法1：动态规划求分组节点算法

输入：满足l－敏感边匿名化G’的邻接矩阵A 和各节点的度矩阵C；匿名化参数k；

输出：分界点矩阵TZ；分组后节点矩阵TZ

2.2.2 贪心算法求分组节点算法

在满足l－敏感边匿名模型的基础上，根据节点度的大小，按节点度从大到小进行排序，采用贪心策略根据节点度进行分组，使得每个组至少包含k个节点。

贪心算法首先将递减度序列的前k 个节点划分为一组，然后依次判断下一个节点是否合并到前面已经形成的分组或者是否作为一个新组的开头。判断的依据为比较以下两个匿名度的损失

式中：II（i，j）——将i到j 的所有节点均变为i节点度的匿名损失度。若KK＜＝KKX，则第 （w＋k＋1）个节点归到前面的分组；若相反，则作为一组新的开头，依次类推，直到处理完所有节点。具体的贪心算法求分组节点算法如算法2所示。

算法2：贪心算法求分组节点算法

输入：满足l－敏感边匿名化G’的邻接矩阵A 和各节点的度矩阵C；匿名化参数k；

1.［x，y］＝sort（C，’descend’）

2.计算将所有节点都变为目标度时的度差矩阵II

3.FOR（w＝ （k＋1）：length（x）－k－1）%贪心算法求分界点

输出：分界点矩阵TZ；分组后节点矩阵TZ

2.2.3 （k2，l）－匿名算法

在满足l－敏感边匿名模型的基础上，首先利用动态规划算法求得分组的分界点。然后，通过添加非敏感边，使每两个组之间至少有k 个节点相连。最后，找到每组中节点度与目标度差最大的节点，添加非敏感边，直到每个组中的节点满足步骤每组选择的目标度，使分组满足 （k2，l）－匿名模型。基于上述讨论，设计了基于动态规划的度序列匿名算法构建 （k2，l）－匿名模型，具体的算法描述如算法3所示。

算法3：（k2，l）－匿名算法

输入：含敏感边的社会网络G 的邻接矩阵result；整数l；

3 实验结果及分析

本实验运行环境为：Microsoft Windows 7Professional操作系统，2GB 内存，2.26GHz CPU，采用Matlab编程实现。

本文采用Pajek 软件 （http：／／vlado.fmf.uniljsi／pub／networks／pajek／）生成的包含多类型边的社会网络图作为本文实验数据集。社会网络图中包含节点数｜V｜＝380，边的数量｜E｜＝630。边的类型分别为同学关系、朋友关系、家人关系3种，本文将家人关系看作节点间的敏感关系。本实验对实现不同匿名模型的运行时间进行了对比分析。通过改变社会网络图的匿名化参数，对通过不同匿名算法实现匿名后的社会网络度信息损失和其性能进行分析对比。

3.1 执行时间分析

如图2为k＝5，l＝2时基于动态规划和贪心算法实现3种不同匿名模型的运行时间比较。从以下两图中均可看出，实现 （k2，l）－匿名模型比实现其它两个匿名模型时间较长，因为 （k2，l）－匿名算法在满足这两个匿名模型的基础上，要求每两组之间至少有k个节点相连，若随机的添加非敏感边，运行时间会减少，却以大量的度信息损失为代价。所以在添加边时通过找到度差最大的节点添加非敏感边，以提高匿名图的可用性。随着数据集的增大、节点数的增多，运行时间也会越来越长。图2 （b）中运行时间比图2 （a）中运行时间较短，在考虑运行时间的同时还要考虑使用不同算法匿名后社会网络图的可用性。以下通过3个方面根据不同匿名参数比较两种算法的可用性，同时对不同匿名模型匿名后的社会网络图可用性进行了分析比较。

图2 不同匿名算法的CPU 运行时间对比

3.2 匿名图的度信息损失分析

在本文的算法中，通过匿名图的度信息损失表示匿名成本。图3、图4为分别通过动态规划和贪心算法实现不同匿名模型的匿名成本随k值变化的情况。图3、图4 （a）和（b）中分别给出了当l为2和3时，各算法的匿名成本随k值变化的情况。当l一定时，随着k值的逐渐增大，匿名度信息损失呈上升趋势，而k－匿名的匿名成本要远小于其它两种匿名算法，但是k－匿名算法只能抵御度的攻击； （k，l）－匿名算法和（k2，l）－匿名算法的匿名度信息损失在k值较小的情况下不相上下，随着k值的增大，（k2，l）－匿名度信息损失要略微高于 （k，l）－匿名算法的度信息损失。当l＝3时，3种匿名算法的匿名成本要大于l为2时的情况。

在图5 中，对通过动态规划和贪心算法实现 （k2，l）－匿名模型的匿名度信息损失进行了比较，在k 值小于6时，两种算法的匿名度信息损失上下相当。在k值大于6时，动态规划实现匿名模型的度信息损失要小于贪心算法。并且随着k值的不断增大，动态规划的优势越来越明显。随着k值和l值的不断增大，社会网络图的匿名效果会越来越好，而社会网络图的可用性会随之降低。所以，用户可以根据自己不同的需求，调整l和k 的值，达到满意的匿名程度。

图3 动态规划实现不同匿名模型随k值变化的度信息损失

图4 贪心算法实现不同匿名模型随k值变化的度信息损失

图5 不同算法的 （k2，l）－匿名模型随k值变化的度信息损失

3.3 平均最短路径差值分析

图6、图7 （a）和 （b），为l分别等于2和3时，平均最短路径差值随k值变化的情况。当l一定时，k－匿名的平均最短路径差值要小于其它两个算法的值，随着k 值不断增大，3种匿名社会网络图的差值呈缓慢上升趋势， （k2，l）－匿名图的平均最短路径差值要略大于 （k，l）－匿名图的平均最短路径差值。而 （k，l）匿名图和 （k2，l）－匿名图的差值都要大于k－匿名图。

图8中两种算法实现 （k2，l）－匿名模型的平均路径差值进行了对比。在k 小于6的情况下，两种算法的平均最短路径差值基本相同，在k 大于6的情况下，随着k 值的增大，基于贪心算法的平均路径差值上升趋势逐渐加快。

3.4 聚类系数差值分析

图9、图10 （a）和 （b），为l分别等于2和3时，聚类系数差值随k值的变化情况。在图9 （a）和图9 （b）可以看出，k－匿名模型的聚类系数差值远小于其它两种匿名模型的差值。在l一定的情况下，随着k值的不断增大，聚类系数差值呈上升趋势，（k2，l）－匿名图的聚类系数差值与 （k，l）－匿名图差值相差较小，随着k 值不断增大，网络图的可用性也随之降低。

图6 动态规划实现不同匿名模型随k值变化的平均路径差值

图7 贪心算法实现不同匿名模型随k值变化的平均路径差值

图8 不同算法的（k2，l）－匿名模型随k值变化的平均路径差值

图9 动态规划实现不同匿名模型随k值变化的聚类系数差值

图10 贪心算法实现不同匿名模型随k值变化的聚类系数差值

图11中，k值小于6时，贪心算法聚类系数差值较小。在k 大于6的情况下，基于动态规划算法的聚类系数差值要较小。在k小于6的情况下，动态规划算法并没有太大的优势，随着k 值得增加，动态规划算法的优势越来越明显，k值大于6的情况下选择基于动态规划算法实现较好。

从以上实验结果中可看出，在k 值和l 值一定的情况下，k－匿名图的可用性最好， （k，l）－匿名图比 （k2，l）－匿名图的可用性略微要好，然而 （k2，l）－匿名图可以进一步的抵御朋友链接攻击。进一步对两种算法的不同系数差值进行分析对比，在k 值小于6的情况下动态规划和贪心算法均可选择，随着k 值不断增大，动态规划算法的优势越来越明显。

在本文中，贪心算法先将递减度序列前k 个节点划分为一组，均变为本组的目标节点，然后考虑后续节点，只是保证了在当前状态下的子序列是最优的，而动态规划算法是将所有节点可能出现的所有分组全部进行比较，比较完后自底向上选择分组节点，在k 值较小的情况下，由于度序列按降序排列，每个组的节点变为本组节点目标度时，每组的度损失相对k 值较大的情况下较小。所以，动态规划算法的优势并不明显，随着k 值不断增大，每个分组的度损失也会相差较多，则优势也会越来越明显。用户可以根据自己的不同需求，根据k值和l值的不同选择不同的匿名算法，在保证社会网络图可用性较好的前提下，达到用户满意的匿名程度。

图11 不同算法的（k2，l）－匿名模型随k值变化的聚类系数差值

4 结束语

为了保证含敏感关系的社会网络中用户的隐私不会被同时存在的多种类型的攻击者获得。设计了 （k2，l）－匿名模型，可同时抵御敏感关系攻击、节点度攻击和朋友连接攻击。分别通过动态规划度序列匿名算法和贪心算法度序列匿名算法实现 （k2，l）－匿名模型，通过比较不同匿名模型的匿名参数，证明 （k2，l）－匿名模型的可行性，并比较不同算法的匿名参数，用户可根据不同参数选择不同的匿名算法，实现 （k2，l）－匿名模型。该方法不仅能够同时抵御敏感关系攻击、度攻击和朋友连接攻击，而且能够合理地控制信息损失度。下一步的研究方向：社会网络是不断发展和变化的，可以考虑社会网络的动态性；随着网络技术的发展，可以考虑采用并行算法对社会网络数据进行分析处理，提高数据匿名化的有效性。

［1］Bhagat S，Cormode G，Krishnamurthy B，et al.Class－based graph anonymization for social network data［C］／／Proc of the 35th Int’l Conf on Very Large Databases，2009：766－777.

［2］LIU Xiangyu，WANG Bin.Survey on privacy preserving tech－niques for publishing social network data ［J］.Journal of Software，2014，25 （3）：142－156 （in Chinese）.［刘向宇，王斌.社会网络数据发布隐私保护技术综述 ［J］.软件学报，2014，25 （3）：142－156.］

［3］Gao J，Xu JY，Jin R，et al.Neighborhood－privacy protected shortest distance computing in cloud ［C］／／Proc of the ACM SIGMOD Int’l Conf on Management of Data，2011：409－420.

［4］YANG Jun，LIU Xiangyu，YANG Xiaochun，et al.Automorphism based k－secure for privacy preserving in social network ［C］／／The 29th China Database Academic Conference，2012：264－271 （in Chinese）. ［杨俊，刘向宇，杨晓春，等.基于图自同构的k－Secure社会网络隐私保护方法 ［C］／／第29届中国数据库学术会议论文集，2012：264－271.］

［5］Zhelea E，Getdoor L.Preserving the privacy of sensitive relationships in graph data ［C］／／Proceedings of the 1st ACM SIGKDD Workshop on Privacy，Security，and Trust in KDD，2007.

［6］LAN Lihui，SUN Yinghui.Privacy preservation of sensitive edges in social networks publication ［J］.Journal of Jilin University，2011，29 （4）：324－331 （in Chinese）. ［兰丽辉，孙英慧.社会网络发布中敏感边的隐私保护 ［J］.吉林大学学报，2011，29 （4）：324－331.］

［7］Li J，Han J M，Luo F W，et al.K－Sensitive edge anonymity model for sensitive relationship preservation on publishing social network ［C］／／The 3rd International Conference on Information Technology and Computer Science，2011：146－149.

［8］Zheleva E，Getoor L.Preserving the privacy of sensitive relationships in graph data ［C］／／Proc of the 1st ACM SIGKDD Workshop on Privacy，Security，and Trust in KDD，2007：153－171.

［9］Campan A，Truta T M，Cooper N.P－sensitive K－anonymity with generalization constraints［J］.Transactions on Data Privacy Journal，2010，3 （2）：65－89.

［10］NAN Lili，WU Tao.Research on information mixing－based protection mechanism in online social networks［J］.Computer Engineering and Design，2011，32 （10）：3278－3283 （in Chinese）.［南丽丽，吴涛.基于信息混淆的社会网络隐私保护 机 制 ［J］. 计 算 机 工 程 与 设 计，2011，32 （10）：3278－3283.］

［11］WANG Xiaohao，GENG Hui.Privacy protection disturbance method of society network based on spectrum constraint and sensitive area division ［J］.Journal of Computer Applications，2013，33 （6）：1608－1611 （in Chinese）. ［王小号，耿惠.基于谱约束和敏感区划分的社会网络隐私保护扰动方法 ［J］.计算机应用，2013，33 （6）：1608－1611.］

［12］ZHANG Jianpei，XIE Jing.A t－closeness privacy model based on sensitive attribute values semantics bucketization ［J］.Journal of Computer Research and Development，2014，51（1）：126－137 （in Chinese）.［张健沛，谢静.基于敏感属性值语义桶分组的t－closeness隐私模型 ［J］.计算机研究与发展，2014，51 （1）：126－137.］

［13］WU Hongwei，ZHANG Renwei.（k，l）－anonymity for social networks publication against composite attacks ［J］.Journal of Harbin University of Science and Technology，2013，18（3）：47－53 （in Chinese）.［吴宏伟，张仁伟.抗复合攻击的社会网络 （k，l）匿名方法 ［J］.哈尔滨理工大学学报，2013，18 （3）：47－53.］