动态网络多次发布中防止标签邻居攻击的匿名方法

摘要

本发明公开一种动态网络多次发布中防止标签邻居攻击的匿名方法，其对每个时刻输入的社会网络数据进行分组，在每次分组时，都把邻居标签相似度最大的节点分到一组，直到所有的带敏感标签的节点分配合适的分组，最后对组内的非敏感标签的个体在匿名社会网络中做隐藏标签处理；分组完成后将生成的分组合并到分组表中，同时对连续发布次数进行判断，仅保证在连续w次发布中，对组内节点的1‑邻居图进行匿名化处理，而超过w次发布时候，则从表内移除t‑w时刻的分组，从而保证数据的可用性和效用性。

说明书

技术领域

本发明涉及数据隐私保护技术领域，具体涉及一种动态网络多次发布中防止标签邻居攻击的匿名方法。

背景技术

社会网络是由许多节点和边构成的一种社会结构，节点通常是指个人或组织，节点之间的连线即边代表个人或组织的相互关系。随着经济的快速发展，社会网络的应用也越来越普及，例如Facebook、LinkinIn等。社会网络中包含着用户有很多的个人信息，例如姓名，性别，年龄，地址，职业。在社会网络图中，属性表示为标签，用户可以选择特定属性信息隐藏，所以标签可以分为敏感和非敏感。最常用且直观的一种匿名方法为简单匿名，即移除能唯一标识用户的显式标识符属性，只保留标签表示属性信息。许多先前的研究已经证实简单匿名不足以保护用户隐私。而现有的研究也仅是基于静态网络设计的通用的隐私保护方法，隐私保护技术集中于研究单次数据发布，而很少是基于动态网络多次发布的用途来设计隐私保护方法。发展变化的社会网络数据动态发布需要动态的隐私保护方法来处理。

发明内容

本发明所要解决的是现有隐私保护的匿名方法仅是基于静态网而设计，而无法适用于动态网络多次发布的问题，提供一种动态网络多次发布中防止标签邻居攻击的匿名方法。

为解决上述问题，本发明是通过以下技术方案实现的：

动态网络多次发布中防止标签邻居攻击的匿名方法，包括如下步骤：

步骤1、设定隐私水平l和时间窗口w，并将分组表GS-Table置为空；

步骤2、初始化当前时刻t原始的社会网络数据；即去掉显示的标识属性，改用标签表示；同时，将节点集合按度数排列，得到新的节点集合；

步骤3、对带敏感标签的节点根据邻居标签相似度进行分组；

步骤3.1、选择新的节点集合中度数最大的带敏感标签的节点，并将该选中的节点从新的节点集合中去除；

步骤3.2、计算选中的带敏感标签的节点和新的节点集合中的每个节点的标签相似度，并将该选中的带敏感标签的节点及其标签相似度最相似的节点归为一组，直到该分组中所包含的节点个数达到隐私水平l；

步骤3.3、重复步骤3.1-3.2，直至新的节点集合中不再含有带敏感标签的节点；

步骤4、完成分组的工作后，将t时刻所生成的分组，合并到分组表GS-Table中；

步骤5、判断当前时刻t是否小于等于时间窗口w；如果t≤w，则返回步骤2；如果t＞w，则从分组表GS-Table中移除t-w时刻所生成的分组；

步骤6、对于分组表GS-Table中的各个分组，对组内所有节点的1-邻居图采用边复制和标签泛化的方法把原始图匿名成同构；

步骤7、发布匿名后的社会网络数据。

上述步骤1中，将节点集合按度数降序排列，得到新的节点序列。

上述方法中，每个时刻t对应一次原始的社会网络数据的更新。

上述方法中，隐私水平l的取值范围介于2～30之间。

上述方法中，时间窗口w的取值范围介于1～10之间。

与现有技术相比，本发明具有如下特点：

(1)本发明在每次分组时，都把邻居标签相似度最大的节点分到一组，直到所有的带敏感标签的节点分配合适的分组，最后对组内的非敏感标签的个体在匿名社会网络中做隐藏标签处理；这样能够保护带敏感标签的节点，使得带敏感标签的节点在匿名前后的改变小，匿名损失最小；

(2)本发明对w次发布的社会网络进行l^w-grouping分组，使之满足动态网络多次发布的匿名要求，t时刻已经分组的节点，t+1时刻不能分到其他组中，这样攻击者就不能通过比对多次发布，使敏感信息泄露；

(3)本发明建立一个GS-Table表，其仅保证在连续w次发布中，对组内节点的1-邻居图进行匿名化处理，而超过w次发布时候，则从表内移除t-w时刻的分组，从而保证数据的可用性和效用性。

附图说明

图1为动态网络多次发布中防止标签邻居攻击的匿名方法的原理图。

图2为动态网络多次发布中防止标签邻居攻击的匿名方法的流程图。

图3为不同时刻输入的社会网络，其中(a)为t＝1时刻输入的社会网络G₁，(b)为t＝2时刻输入的社会网络G₂，(c)为t＝3时刻输入的社会网络G₃。

图4为不同时刻匿名后的社会网络，其中(a)为t＝2时刻匿名社会网络G₂’，(b)为t＝3时刻匿名社会网络G₃’。

具体实施方式

本发明用到的社会网络数据是带标签的简单无向图，攻击者的背景知识可以是任意节点所在的特定的子图信息，即邻居标签信息。社会网络数据在发布前需要进行初步的匿名处理，即去掉唯一标识节点的显示标识属性，如姓名等，改用标签表示属性信息。发布的图用G_t(V^t；E^t；L^t)表示动态网络t时刻的图，其中V^t为节点的集合，表示社会网络中的个人或其他实体；E^t表示个体之间的关联，即图中边的集合，表示个人或实体间的关系，如朋友、合作关系；L^t表示个体的标签的集合。

本发明提出了一个动态网络多次发布隐私模型，即l^w-graphic-diversity。该l^w-graphic-diversity模型给定一个在时刻t带标签的动态网络G_t(V^t；V_s^t；E^t；L^t)和一个隐私阈值l。其中V^t表示节点的集合；V_s^t表示带敏感标签的节点的集合；E^t表示边的集合；L^t表示个体的标签的集合；Γ表示节点到标签的映射关系，Γ:V^t→L^t。在这个模型中，把节点邻居标签信息作为攻击者的背景知识，个体自身的敏感标签，作为用户需要保护的敏感信息，就是将原始网络G_t转化为局部扰乱的匿名社会网络G_t’，使匿名后的网络在动态发布中满足l-多样性要求。在动态发布的社会网络经过本发明的匿名方法处理，能够有效防止攻击者使用背景知识对用户所在的发布的数据中重新定位。

参见图1，本发明所设计的动态网络多次发布中防止标签邻居攻击的匿名方法，其主要的数据处理过程为：

首先是初始化数据，即去掉显示的标识属性，改用标签表示。除此之外，再将节点集合V^t按度数降序排列，得到新的节点序列。

接下来是对带敏感标签的节点根据邻居标签相似度进行分组，在此过程中：先选择第一个带敏感标签节点，这里选择当前节点列表中度数最大的敏感节点，此时节点集合V^t中除去已选中的节点。后计算这个节点和V^t中的每个节点的标签相似度，选择最相似的节点放在一组，直到组中节点包含的节点个数达到隐私水平l。再选择下一个带敏感标签的节点，重复以上步骤直到剩下的节点集合V的个数小于l，候选集中的节点表示准备选到组中的带敏感标签的节点集。直到候选节点集合为空，此时所有的敏感标签节点分到邻居标签信息相似度最大的组。但如果存在组g中带标签个体个数小于l，则从组集中移除组g_i，并且将组中的节点分到和组中节点有最大标签相似度的其他的组中去。

完成分组的工作后，将生成的组集C^t，即t时刻所有g_i的集合，合并到GS-Table中去，要保证w时刻内隐私得到保护，对组内节点的1-邻居图通过边复制和标签泛化的方法把原始图匿名成同构，最后发布匿名后的社会网络数据。

为解决连续发布动态网络的隐私问题，同时也保证数据效用性，本发明建立一个分组表GS-Table，只保证连续w次发布中，对组内节点的1-邻居图进行匿名化处理；而超过w时间，则从表内移除t-w时刻的分组。GS-Table是有组集构成，t＝1时刻的组集记为C¹，即将带标签节点按照标签相似度进行分组，直到带敏感标签的节点所在候选集为空，分组操作结束。组集中包含的组g_i，每个组中包含的是l个带不同标签的节点集，红色标记的是带敏感标签的节点，黑色是带非敏感标签的节点。每个组中包含不少于1个带敏感标签的节点。组中的节点在发布社会网络匿名图时，组内节点标签要全部隐藏。t＝2时刻的组集记为C²，C¹组集g_i中已经分过组的节点，不能在C²组集的其他组中出现。t＝2时刻和组g_i中节点有最大邻居标签相似度，但还未分到任何组中，通过分组，加入到C¹组集g_i中，生成C²组集中的g_i’。直到w次连续后，GS-Table构建完成。对于t＝2时刻的新添加的带敏感标签的节点，也进行分组操作，不能分到任何现有的组中，新添加的带敏感节点要根据分组算法单独分到新创建的组中，保证组内新添加节点不少于l个带不同标签的个体，并且保证组内节点全是新添加的节点。当t＞w时，移除t＝1时刻的C¹，在满足以上隐私要求条件下，更新C^t组集中的节点。保证了数据的可用性。

下面通过一个具体的实例来对本发明进行进一步说明：

例：时间窗口w设为2。其中g₁中的节点V₁和g₂中的节点V₃是带敏感标签的节点，其他节点是不带敏感标签的个体。如表1，t＝1时刻对每个带敏感标签的个体划分到邻居标签相似度最大的组中。如表2，t＝2时刻对节点重新分组，得到新的分组，此时GS-Table中包括C¹，C²。如表3，t＝3时刻将t＝1时刻在GS-Table的分组移除，再对节点进行重新分组，此时GS-Table中包括C²，C³。t＝2时刻需要匿名的节点就是g_i∪g_i’中所有的节点。

针对动态社会网络多次发布防止标签邻居攻击用途中这一具体应用，本发明提出了一种满足动态社会网络数据隐私匿名方法，即动态网络多次发布中防止标签邻居攻击的匿名方法，如图2所示，主要的实现过程如下：

步骤1：初始化数据集，输入社会网络G^t，参数隐私水平l，时间窗口w，分组表GS-Table。每个时刻t对应一次原始的社会网络数据的更新。图3为不同时刻输入的社会网络G_t，t＝1，2，3，w＝2，l＝2。

步骤2：将GS-Table置为空，将节点集合V^t按度数进行降序排列，以方便后续程序中节点的选择。

步骤3：判断当前时刻t是否小于等于w，若是，则转到步骤4。否则转到步骤9。

由于算法在进行第一分组之前，当前时刻t＝1即连续发布次数必定小于等于设定的时间窗口w，因此在具体的算法编译上，步骤3关于w与w判断的步骤，可以在每次分组步骤运行之前进行，也可以在每次完成分组步骤之后进行，且并不会影响本发明实现效果。

在步骤3中，从以下两方面防止多次发布邻居标签信息攻击，同时保证数据的效用性：

在选择带敏感标签节点分组时，如果t＝1时刻已经分组的节点，t＝2时刻不能分到其他组里面去，有效防止了通过比对多次发布的社会网络而造成了信息的泄露。

对于t时刻的新添加的带敏感标签的节点，也进行分组操作，不能分到任何现有的组中，新添加的带敏感节点要根据分组算法单独分到新创建的组中，保证组内新添加节点不少于隐私水平l个带不同标签的个体，并且保证组内任意节点是新添加的节点，带有相似的邻居标签信息。当t＞w时，移除t-w+1时刻的组集，在满足以上隐私要求条件下，更新C^t组集中的节点，t-w+1时刻不需要再匿名的带非敏感标签的节点保持在t-1时刻的匿名状态，保证了数据的可用性。

步骤4：判断当前的带敏感标签的节点集V_s^t是否为空。若为空，则转到步骤5。否则转到步骤10。

步骤5：选择V_s^t中带敏感标签的节点U_s，即要找到g_i的第一个节点Us；则当前的分组即为g_i＝{U_s}。

步骤6：判断当前的分组中的节点个数是否小于隐私水平l。如果小于l，则转到步骤7。否则转到步骤11。

步骤7：判断当前的候选集节点个数是否大于0。如果大于0，则转到步骤8。否则转到步骤11。只有节点的标签不在当前g_i中，节点才会合并到候选集中。

步骤8：计算当前的带敏感标签的节点和候选节点集中各节点的邻居标签相似度，得到和带敏感标签的节点有最大邻居标签相似度的节点合并到当前的分组g_i中，同时V^t＝V^t-{Umax}。

为了使得每个组内的节点有相同的邻居标签信息，我们对节点进行适当的分组，所以在相同组内的1-邻居图和标签信息是同构的。带有非敏感标签的节点需要插入图中，使得节点的标签邻居图在每个组内是同构的，并且组内节点不少于l个。我们用以下指标对节点进行分组：邻居标签相似度(NLSS)。对于两个节点，v1的邻居标签信息(NLS_v1)和v2的邻居标签信息(NLS_v2)，他们的邻居标签信息相似度可以计算为：

在t＝1时刻，由于当前的带敏感标签的节点V_s^t不为空，所以选择第一个带敏感标签的节点Us，此时选择X，则g₁＝{X}，|g₁|小于l，候选节点集中的节点要和X的标签属性不同，且候选集中的节点数不为空，从候选节点集中选取和X的邻居标签相似度最大的节点，依次计算NLSS(X，V_i^t)，得到max(NLSS(X，Y))＝3/3＝1，即他们有相同的邻居标签信息，邻居标签序列都为B，D，T，依据算法，选择候选集合中的节点Y，g₁＝g₁∪{Y}，当前的V^t＝V^t-{Y}，g₁组中的节点个数不小于l，此时C¹＝C¹∪{g₁}，如果g_i中的节点数少于l，则将组中的节点按照邻居标签信息相似度，找到同组中节点有最大标签相似度的组中去。

在t＝2时刻，从候选节点集中选取和的标签相似度最大的节点，依次计算NLSS(X，V_i^t)，得到max(NLSS(X，Z))＝4/4＝1，即他们有相同的邻居标签信息，邻居标签序列都为B，B，D，T，依据算法，选择候选集合中的节点Z，g₁＝g₁∪{Z}，当前的V^t＝V^t-{Z}，g₁组中的节点个数不小于l，此时C²＝C²∪{g₁}，如果gi中的节点数少于l，则将组中的节点按照邻居标签相似度，找到同组中节点有最大标签相似度的组中去。必须指出的是在发布社会网络图中，分组的节点要进行标签隐藏处理。

步骤9：超过w时间，从表内移除t-w时刻的分组，从GS-Table中移除t-w时刻内的组集C^t。

步骤10：将不少于l个不同的标签的分组g_i合并到C^t中。

步骤11：判断分组g_i中的节点个数是否小于l。如果是的话转到步骤13，否则转到步骤2。

步骤12：从C^t中移除当前g_i，将组中的节点分到同u有最大邻居标签信息相似度的其他组中。

步骤13：将C^t合并到GS-Table中。

我们建立一个GS-Table表，只保证连续2次发布中，对组内节点的1-邻居图进行匿名化处理，超过w＝2时刻，从表内移除t＝1时刻的分组。t＝1时刻得到C¹的节点集合为{X，Y}，此时GS-Table中包括C¹，在t＝2时刻得到C²中的节点集合为{X，Z}，将C²合并到GS-Table，此时GS-Table中包括C¹和C²，即在t＝2时刻要对{X，Y，Z}做边复制标签泛化的匿名化处理。只要t≤w，我们会一直构建GS-Table。在t＝3时刻，其中t＞w＝2，将t＝1时刻中的C¹移除，并将t＝3时刻的邻居标签相似度得到的分组C³合并到GS-Table中。t＝3时刻只要对{X，Z}做边复制标签泛化的匿名化处理，对于Y节点t＝3时刻，不再进行接下来的匿名操作。

步骤14：对组内所有节点的1-邻居图通过边复制和标签泛化把原始图匿名成同构。

t＝1时刻原始图满足2-graphic-diversity，对于每个带敏感标签的节点Us，至少有1个有相同标签邻居图的节点，但节点本身带不同的标签。攻击者不能高于1/2的概率识别带敏感标签的个体X。在图中节点X带有敏感标签，同时，X和Y有相同的1-邻居图，邻居标签信息也相同，即邻居标签都为B，D，T。GS-Table中，{X，Y}在组g₁中。且在t＝1时刻有相同的邻居结构，所以他们是不可区分的。

t＝2时刻原始图中带敏感标签的节点X的邻居标签信息发生变化，为B，B，D，T。为使带敏感标签的个体不被泄露，敏感标签节点分组和l^w-grouping算法产生的邻居标签相似度最大的节点集{X，Y，Z}，将X，Y，Z的1-邻居图做边插入和标签泛化的算法，匿名为同构。其中将节点v_i的所有一步邻居节点集合和这些节点间的边的集合称为节点v_i的1-邻居图。边插入是为了保证节点的邻居标签结构相似，我们先匹配标签后匹配节点的度，t＝2时刻节点X新认识了标签为B，度为1的节点，t＝2匿名图中我们选择一个未匹配的带非敏感标签的节点，标签同样为B，度为2的节点与Y之间插入边。之后插入其他边使得X，Y，Z的1-邻居结构图为同构的。参见图4(a)。

t＝3时刻对节点集{X，Z}中节点X，Z的1-邻居图通过边插入和标签泛化的算法，匿名为同构。Y节点的1-邻居结构保持在t＝2时刻匿名图的状态。因为只要保证连续2次发布中，对组内节点的1-邻居图进行匿名化处理，超过t＝2时刻，从表内移除t＝1时刻的分组。参见图4(b)。

步骤15：结束。

下面通过一个具体实例对本发明进行进一步说明：

以下为本发明方法在本例中的社会网络图数据匿名前后保护带敏感标签个体的情况。

t＝1，t＝2时刻如果攻击者知道个体X的1-邻居结构图，因为个体Z也有相同的标签-邻居图，攻击者不能以高于1/2的概率识别个体X，通过比对两次发布的社会网络图，攻击者不能唯一确定个体X及她的属性L，因为X不是是唯一的节点度发生变化，个体及她的职业不会被泄露。

t＝2，t＝3时刻如果攻击者知道X的1-邻居结构图，因为Z也有相同的标签-邻居图，攻击者不能以高于1/2的概率识别个体X，通过比对两次发布的社会网络图，攻击者不能唯一确定个体X及她的属性L，因为个体X不是是唯一的节点度发生变化，个体及她的职业不会被泄露。