图数据连续发布中的隐私保护方法

朱黎明，丁晓波，龚国强

（1.三峡大学 计算机与信息学院，湖北 宜昌 443002；2.湖北省建筑质量检测装备工程技术研究中心，湖北 宜昌 443000）

0 概述

现有许多基于k 度匿名的社交网络匿名模型都假设网络结构不变，仅考虑网络结构的一次性匿名发布。但是，真实社交网络图是不断变化的，攻击者很有可能根据社交网络图前后的变化进行关联攻击，此外，若每次对待发布数据重新进行一次匿名处理，将降低动态社交网络数据匿名的灵活性，因此，考虑社交网络发布数据的动态性十分有必要，研究人员在动态社区发现［1］、动态社交网络节点影响力［2］、动态社交网络表示学习［3］等领域，都需要对动态社交网络进行深入分析，而隐私保护问题与人们的日常生活密切相关，研究动态社交网络的隐私保护问题和隐私保护方法尤为重要。

针对单一社交网络隐私保护问题，LIU 等［4］提出一种k 度匿名保护方案，其通过构造k 度向量来进行图重构，以防止节点度数攻击，但是，该图重构技术极大地破坏了原图中所有的节点关联关系，带来了很大的结构信息损失。TAI 等［5］提出了k2匿名方法，该方法通过构造k 个具有相同度序列的邻居来防止依据好友身份进行的关联攻击。HAY 等［6］提出了k-candidate 匿名模型，用于防止顶点度数识别攻击，并提出了基于聚类的匿名保护方案。ZΟU［7］和CHENG 等［8］通过研究社交图的子图结构，以对子图分别进行k 同构和自同构构造，它们的不足之处在于需要同构判断以及重构时的代价非常巨大。龚卫华等［9］根据k 度匿名提出SimilarGraph 模型，该模型先对度序列进行簇划分，然后通过边修改操作进行图重构，其操作与k 度匿名模型类似。MITTAL 等［10］提出基于随机游走的匿名技术以保护边链接隐私，用户i和j之间的一条边被用户i和u之间的边替代，其中，用户u是用户j随机游走到达的目的地。王路宁等［11］提出基于链路预测的方法，以对动态数据进行聚类泛化保护。MA 等［12］提出KDVEM 模型，其通过计算最小匿名代价，先对原图进行边修改操作，然后针对无法通过边修改操作达到k 匿名性要求的节点，创建虚拟节点并与该节点建立边，从而实现原始图中所有节点的k 度匿名。周克涛等［13］提出了改进的基于邻居度序列相似度的k 度匿名保护方法，其能抵抗基于邻居度序列的背景知识攻击。CHESTER［14］提出基于虚拟节点的k 度匿名方法，其通过添加虚拟节点使得任意节点满足k 度匿名，并给出所添加节点数量的最小值以及为节点添加的最少下界，通过添加最少的下界使得原图满足k 度匿名性，再对新添节点进行k 度匿名。CASAS-RΟMA等［15］为了适应大型社交网络的k 匿名化，提出单变量微聚合k 级匿名算法，该算法通过边缘相关性测度保留重要的边，减少了信息损失。CHEN 等［16］在k 度匿名的基础上进行改进，通过最小的边编辑方法给出所有图修改操作，使得匿名图尽可能与原图相似。谷勇浩等［17］针对社交网络动态变化的特性，提出基于聚类的动态社交网络隐私保护方法，该方法通过计算聚类间的距离，将变化后的节点重新分配到聚类集合中，然后对变化的节点进行匿名处理。

董祥祥等［18］针对社交网络动态变化的更新问题，提出动态社交网络发布的匿名数据方法，其通过匿名更新已经匿名的数据，保证前后匿名图具有相似的图结构，但是，该方法并未考虑前后匿名图存在的隐私泄露风险。金叶等［19］考虑网络中社区结构属性所带来的隐私泄露风险，将节点分为边缘节点和一般节点，然后对其进行匿名，从而保护度结构和社区结构。KIABΟD 等［20］考虑每次构造k 度向量会浪费很多时间，其通过构造k 度向量树来保证在需要得到不同k 值时可以从k 度向量树上直接得到k 度向量，从而大幅节省重新获取k 度向量的时间。刘振鹏等［21］提出动态社交网络差分隐私保护方法，其缩短了每一次更新匿名图的时间，但是，差分隐私对度背景知识攻击的抵抗性较差，需要添加较多的噪声节点。张晓琳等［22］针对有向社交网络提出大规模出入度匿名保护方法，其通过贪心算法分组并增加虚拟节点来匿名节点，在对虚拟节点进行合并删除的过程中依据层次社区结构划分保持节点所属社区不变，从而较好地保护图的基本属性和社区结构。

上述大多数度匿名研究集中在单一社交网络匿名保护方面，虽然可以对变化后的整个社交网络重新匿名再进行发布，但是这样的匿名方式会存在大量冗余计算，有少量节点和边发生变化时还是需要对整个社交网络进行全部匿名化处理。此外，攻击者在分析前后匿名图中的节点度变化时，根据前后不同时刻的匿名图进行关联攻击，这存在一定的隐私泄露风险。针对上述问题，本文提出一种图数据连续发布中的k 度时序匿名方法。考虑连续图中节点度数变化会泄露隐私的问题，通过构造k 度时序矩阵来保证前后匿名图中节点度变化相同的节点个数不少于k 个，然后通过图修改方法得到一系列匿名图版本。

1 问题描述及相关定义

本文考虑的时序图是无向无权的简单图的连续变化过程，用G={G1,G2,…,GT}表示图的变化过程，在t时刻的社 交网络图为Gt={Vt,Εt}(1 ＜t＜T)，Vt和Εt表示t时刻图中的节点和边，对于每个节点而言，不同时间段其度可能发生变化。尽管当前社交网络已经满足k 度匿名性要求，但是，在有新的节点加入时，会破坏原有匿名图的匿名性，这时需要重新对社交图进行匿名化处理。此外，根据前后匿名图，攻击者有一定几率能识别出特定的节点，导致该节点被唯一标识，进而导致隐私泄露，本文将其定义为度时序背景知识攻击。

定义1（度时序背景知识攻击）度时序背景知识攻击也称度变化背景知识攻击，当攻击者具有较强的度背景知识时，通过已知节点在不同时刻社交网络中度数变化的唯一性，可以标识该节点。

定义1 增强了攻击者的攻击能力，为了更好地说明度时序攻击的可能性，本文给出简单的示例，如图1 所示，t0时刻图G0节点度序列为[3,3,2,2,1,1]，其为2 度匿名图，当有新的节点ν7和ν8加入时，得到t1时刻图G1，G1的节点度序列为[3,3,3,3,2,1,2,1]，也是一个2 度匿名图。以度矩阵D的形式可以更直观地体现各个节点度的变化情况，后续将D定义成度时序矩阵，其中，各个节点的度变化依次为［3，3］、［3，3］、［2，3］、［2，3］、［1，2］、［1，1］、［0，2］、［0，1］，共同组建成D，0 表示该节点未出现在该时刻的图中。当攻击者知道节点ν5的度数由1 变成2、节点ν7的度数由0 变成2、节点ν8的度数由0 变成1 时，由于这些节点度的变化在匿名图中唯一，则攻击者就能够以很高的概率唯一标识这些节点，导致这些节点标识隐私泄露，由此可见，满足k 度匿名并不能抵抗度时序背景知识攻击。

图1 不同时刻的2 度匿名图Fig.1 2-degree anonymous graph at different times

由以上例子可以看出，在不同时间段，节点的度数会发生变化。为了更好地解决节点度数变化可能导致的隐私问题，本文将度变化定义成度时序，具体如定义2 所示。在多个社交网络中，不同用户在不同时刻图中的度数组成度时序矩阵，具体如定义3所示。

定义2（度时序）在连续的图数据发布中，节点的度数在不同时刻社交图中会出现不同的值，节点度会随着时间的变化而改变。节点i的度时序用Di·=[di1,di2,…,dit,…,diT]表示，其中，dit表示在时间t发布的社交网络Gt中节点i的度数。

定义3（度时序矩阵）由各个节点的度时序向量共同组成的矩阵称为度时序矩阵Dn×T，其中，n表示连续社交网络中节点的最大值，T表示连续社交网络中的图个数。图1 中的8×2 矩阵D为度时序矩阵。

定义2 和定义3 是对原始多个待发布图的特征定义，考虑到攻击者会根据度变化的唯一性进行攻击，从而导致隐私泄露，因此，需要保证至少有k-1个节点的度时序相同，这样才能满足k 匿名性要求。

定义4（k 度时序匿名）在连续发布图中，对于任意一个节点ν的度时序，至少存在k-1 个节点的度时序与之相同。

定义4 是传统k 匿名保护方法的扩展，其能抵抗更强的背景知识攻击，又同时具备原有k 匿名方法的隐私保护能力。

定理1若社交网络图满足k 度时序匿名，则满足每个时刻的社交图是k 度匿名的。

证明在k 度时序匿名的连续图中，对于任意一个节点ν，由于其满足k 度时序匿名，则必定存在k-1 个节点的度时序向量是相同的，因此，在对应的时刻图中，节点ν的度数至少与k-1 个节点的度是相同的，满足k 度匿名性，因此，k 度时序匿名的时序图中每一时刻的社交图都是k 度匿名的。

由定理1 可知，满足k 度时序匿名一定满足k 度匿名，简单而言，就是在能够抵抗度攻击的基础上，还可以抵抗攻击者根据度变化进行的攻击。

定义5（k 度时序矩阵）如果连续图数据发布中的度时序矩阵是k 度时序矩阵，那么在由节点度时序向量组成的度时序矩阵中，对于任意一个节点的度时序向量，至少有k-1 个节点的度时序向量与之相同，即在度时序矩阵中，对于任意一行，至少有k-1 行与其相同。

由定义5 可以看出，本文参考k 度匿名算法中的简易思想原理，通过提取每个节点的度时序组成度时序矩阵，使度时序矩阵中的每一个行向量都有至少k-1 个行向量与之相同，那么连续图数据就是k 度时序匿名的。在得到满足k 匿名性的矩阵后，通过图修改技术对原始图进行边和节点的修改操作，就可以得到所需的匿名图并进行发布。

2 连续图中的k 度时序匿名模型

为了满足图数据连续发布中的k 度时序匿名性，本文提出连续图k 度时序匿名模型，其算法分为两步：首先，获取整个连续图数据的度时序矩阵D，基于贪心策略进行度时序矩阵分组划分，获取连续图的目标度时序矩阵D′；其次，为了减少冗余计算，对已经匿名处理的图进行图修改操作，结合t-1 时刻匿名图和t时刻的k 度向量，对下一时刻的原图Gt进行匿名化处理。为了更好地说明本文模型与传统模型之间的差别，给出两者的流程比较，如图2 所示。

图2 2 种匿名模型的对比Fig.2 Comparison of two anonymous models

从图2 可以看出，对于多个待发布的图数据而言，其k 度匿名模型需要对每一个待发布图都进行匿名处理，这在很大程度上浪费了时间，而且不能很好地抵抗度时序攻击，而k 度时序匿名不仅可以抵抗度时序攻击，还可以更好地处理多个待发布图，在增强隐私的同时更具灵活性。

2.1 基于贪婪划分策略的k 度时序矩阵构造

对于社交图的变化情况，本文考虑符合人们真实活动的社交网络，即某一用户在原社交圈认识新的朋友对应社交图中边的增加，有新的成员加入该社交圈子对应新节点的增加和新边的增加。对于图1 中的D而言，其不满足2 度时序矩阵的要求，因此，首先要将其转换成2 度时序矩阵，转化后各个节点的度变化依次为［3，3］、［3，3］、［2，3］、［2，3］、［1，2］、［1，2］、［0，2］、［0，2］，这些变化共同组成D′。由此可见，D′中至少存在2 个相同的向量，是一个2 度时序矩阵，攻击者就无法以高于1/2 的概率识别出具体节点，同时在每个时刻的图中也不可能进行度攻击。

基于以上考虑，对于度时序矩阵D，本文首先要将其划分成多个组，其中，每个组中至少包含k 个行向量，使得每个行向量直接转换成相同向量产生的匿名代价最小，因此，可以参考k 度匿名中对一维度序列的贪婪划分策略［4］，将距离测度较小的向量合并到同一分组中，节点i和节点j的距离测度为：

其中：Di·表示度时序矩阵的第i行；Dj·表示第j行；||·||1表示行向量的1 范数。对于分组中含有不同的行向量，统一选取产生1 范数最大的行向量作为整个组的匿名标准（这一点与k 度匿名选取最大度作为分组的匿名标准相似），对分组进行统一匿名化，具体操作如算法1 所示。

算法1基于贪婪策略的分组划分算法

2.2 基于图修改的k 度时序匿名方法

在经过贪婪分组划分后，得到满足k 匿名性的k 度时序矩阵，接下来根据图修改方法将连续社交图G转化成满足匿名性的连续图G′。对第一时刻的匿名图G1，可以采用已有研究中的任何k 度匿名算法进行匿名操作，如何降低其对后续社交网络的匿名处理时间是研究重点。首先，计算后续匿名图与已匿名图之间的差异，即k 度时序矩阵中当前列与下一列的差值，当两者中的某些元素相同时，表示这些节点不需要进一步处理，当不相同时，需要对当前匿名图对应的节点进行匿名处理，从而得到下一时刻的匿名图。因此，首先计算当前匿名图的k 度向量与下一个待匿名图对应节点的差值：

如图3 所示，由于图1 中连续社交网络并不满足2 度时序匿名性，因此需要对其进行匿名化处理。首先根据D′得到需要匿名的节点ν6和ν8都需要增加1 度，通过图修改方法可以直接在2 个节点之间增加一条边，如图3（b）所示，曲线即为添加的边。

图3 2 度时序匿名图Fig.3 2-degree time series anonymous graph

通过图修改操作来增加边的过程为：如果节点i和节点j都需要增加度，并且i和j之间不存在边，则添加一条边（i，j）。通过图修改操作来增加虚拟节点的过程为：如果节点i和节点j都需要增加度，但i和j之间存在边，则创建虚拟节点k，其与节点i、j都相连。具体匿名步骤如算法2 所示。

算法2k 度时序匿名算法

在算法2 中：步骤3～步骤9 主要计算各个已匿名节点达到下一时刻匿名要求的差值，并将其保存到候选节点中；步骤10～步骤23 是对当前已经满足k 度匿名性的图进行修改，包括添加边和添加虚拟节点，使其成为满足下一时刻匿名要求的k 度匿名图。算法整体的时间复杂度为Ο（n+c2+c），c表示下一时刻需要匿名的节点个数，待修改节点集合可以提前计算并保存，因此，图修改方法的时间复杂度为Ο（c2+c）。而对于传统k 度匿名重构算法而言，由于需要根据k 度向量重新构造匿名图，因此每次都需要重新匿名处理，时间复杂度为Ο（T·kn），其中，kn为处理单个社交图的匿名算法的复杂度［4］，T表示社交图个数。因此，在匿名算法复杂度方面，本文算法性能较优。

3 实验分析

本文从运行时间和数据属性实用性2 个方面验证所提匿名算法的可行性，同时将其与传统kDA 算法［4］进行比较。kDA 算法是单一时刻社交网络图数据匿名算法，为了使其能够适应图数据连续发布中的度匿名保护，需要对每个时刻的社交图都进行一次kDA 算法操作，以此得到整个连续社交图在各个匿名算法下的实验数据。所有实验都是在Windows10 操作系统下进行，配置为16 GB 的RAM、3.40 GHz 的八核处理器i7-6700，编译环境为Python3.6。

3.1 数据集

本文实验使用Facebook 数据集，该数据集从斯坦福大学数据库SNAP（http：//snap.stanford.edu/data/index.html）中得到，共包含4 039 个节点，88 234 条边。由于该数据集是单个社交图，因此本文通过随机增加节点以及增加具有相同邻居的节点之间的边，以模拟图数据连续发布过程。处理后的数据集具体信息如表1 所示。

表1 Facebook 数据集信息Table 1 Facebook dataset information

3.2 结果分析

为了验证本文算法的有效性，首先，从运行效率上将其与kDA 算法［4］进行对比，运行时间为各个社交图匿名时间的总和。其次，本文将图结构的平均聚类系数、平均路径长度、传导性等［23］图结构属性作为评价指标，通过实验来验证本文算法的数据实用性。

图4 所示为本文算法和kDA 算法的总体运行时间对比，其中，kDA 算法的时间是匿名不同时刻社交图的时间总和。从图4 可以看出，随着隐私程度k 值的不断增大，算法处理的节点数量不断增多，因此，2 个算法的总体运行时间都在增加，但是本文所提算法的运行时间总体上都小于kDA 算法，这是因为在后续处理匿名图时，本文算法可以在第一个匿名图的基础上进行图修改操作，以得到后续的匿名图，大幅减少了所处理节点的数量，而kDA 算法要重新遍历整个原始图进行重构操作，在很大程度上浪费了时间。因此，本文所提算法总体运行时间优于kDA 算法。图5 所示为本文算法和kDA 算法在不同数据集上通过匿名操作引起的平均聚类系数变化。从图5 可以看出，随着隐私程度k 的不断增大，2 种算法都会改变原始图的平均聚类系数，但是，kDA 算法中的重构匿名在较大程度上改变了原图的平均聚类系数，而本文所提算法在原始图的基础上进行图修改，改变平均聚类系数较少，虽然两者改变程度相似，但是本文算法对度时序背景知识攻击具有很好的抵抗性，相当于增强了原始图抵抗去匿名化的能力，本文通过图修改方法较少地改变了平均聚类系数属性，较好地保留了原始图结构，能够更好地抵抗度时序背景知识攻击。

图4 2 种算法的运行时间对比Fig.4 Comparison of running time of two algorithms

图5 平均聚类系数变化情况Fig.5 Change of average clustering coefficient

图6 所示为在不同时刻社交图上通过匿名操作后引起的平均最短路径变化。从图6 可以看出，随着匿名程度的增加，2 个算法引起平均最短路径的变化越来越大，但是，kDA 算法引起的变化较大，这是因为在图重构算法中重构具有随机性，并且会存在强行改变原始图节点分布的情况，较大地改变了平均路径长度，而本文算法分析边操作满足不了k 匿名性的问题，对无法通过边操作的节点，通过构建虚拟节点来满足k 匿名性，这就增大或者减小了一些节点的最短路径长度，平均最短路径长度变化较小，从而较好地保留了数据实用性。

图6 平均最短路径变化情况Fig.6 Change of average shortest path

图7 所示为2 种算法中图的传导性相对于隐私程度k 的变化情况。从图7 可以看出，随着k 值的增加，2 种算法都轻微地影响原图传导性的值，相对于其他图结构属性而言，传导性影响较小，但是，本文算法的影响程度总是小于kDA 算法，其较好地保留了原图的结构属性。

图7 传导性变化情况Fig.7 Change of conductivity

为了更好地说明本文匿名算法的性能，将2 个算法的总体边变化率的平均值进行比较，如图8 所示。从图8 可以看出，kDA 算法较大地改变了原始图中的边，这是因为重构算法是根据目标度序列重新生成匿名图，原有节点的边可能在重构中转换成与其他节点相连的边，这就导致图中原有边发生较大改变。而本文算法是在原图的基础上进行修改，保证了原有边不会发生改变，较好地保留了原始边，因此，在边的改变情况上体现出性能优势。

图8 总体边变化率Fig.8 Overall edge change rate

4 结束语

传统k 度匿名在连续社交网络发布中存在隐私泄露风险，为了保证节点度变化的k 匿名性，本文提出一种k 度时序匿名保护方法。通过提取每个节点在每个时刻图中的度时序矩阵，构建满足k 匿名性要求的k 度时序矩阵，利用图修改技术进行匿名化处理，完成每个时刻社交图的k 度时序匿名，匿名后的图不仅在每个时刻都满足k 度匿名的要求，而且可以抵抗攻击者基于节点度变化进行的推理攻击，加强了节点在连续发布图中的匿名强度。实验结果验证了该方法在运行效率上的优势以及在图结构属性上的可用性。本文方法在对社交图进行匿名保护时引起的结构属性变化较大，后续将研究如何通过较小的图结构属性改变来满足图数据连续发布中的匿名保护要求。