一种面向大规模图数据发布的隐私保护方法及系统

摘要

本发明公开了一种面向大规模图数据发布的隐私保护方法，具体为(1)将原图数据均匀地划分多个子块；(2)读取被切割连边，比较被切割连边两端的节点度大小，在节点度较大的节点所属子块内新增噪声节点，通过节点度较大的节点与噪声节点连线实现对被切割连边的保留；(3)构造出同构块矩阵；将子块结构信息与同构块矩阵比较，并以添加噪声边的方式进行同构，完成图数据匿名保护。本发明将整体的图数据匿名保护所需时间降低了一个数量级，做到了匿名化过程的高效性；最终的匿名图满足k匿名机制，做到了匿名化的安全性。该发明保证了匿名图在可用性，安全性，高效性三者的平衡性能大幅度提升。

说明书

技术领域

本发明属于图数据处理技术领域，更具体地，涉及一种面向大规模图数据发布的隐私保护方法及系统。

背景技术

近年来，随着多方共享数据规模的爆炸式增长，无论是学术界或是工业界，都迫切需要大规模数据处理技术，尤其是对于像大规模图数据的这类非结构化数据。由于图数据的结构特性，其在众多数据存储分析领域得到广泛运用。例如Facebook采用TAO系统存储其超大规模的社会网络数据。然而像这类的社会网络数据包含了大量的用户个人隐私信息，数据拥有者在发布和分享这些数据给第三方之前需要对原数据进行特殊的隐私保护处理。通常说来，简单地将原图数据去除用户ID来保护隐私，攻击者仍旧能够基于已知的背景知识轻易地识别出图数据上的个体，并且获取其相关的隐私信息。而这类重识别攻击风险可大致划分为三类：1、身份泄露风险：个体能够通过其对应的邻居节点信息被唯一识别；2、成员泄露风险：各个成员间的关联信息泄露；3、内容泄露风险：个体敏感属性或者个体间连接的敏感信息泄露。因此，保护图数据上的隐私信息至关重要。

目前，针对图数据的隐私保护主要方式之一是k匿名机制。k匿名机制其目的在于确保图上个体被识别出来概率最大为1/k,匿名图的可用性以及其安全性二者的平衡依赖于k值的大小。而k匿名的突出优势在于其允许数据拥有者修改原图上的结构信息并且发布整个匿名后的图结构信息给任意的第三方。但现有基于k匿名机制的隐私保护方案存在有以下突出问题：1、效率低，匿名化周期长：由于现有技术花费大量的时间在图分割过程中，使得匿名方案整体效率性大幅度下降；2、可用性差：现有技术可用性受制于图分割的优劣，由于图分割的不确定性，往往匿名过程需要添加大量的噪声信息以及删除原图上的信息，使得匿名图的可用性随机性大，可用性差；3、平衡性差：现有匿名方案往往着重于方案的可用性或高效性上，缺乏对于可用性、高效性以及安全性三者间动态平衡的保障。

发明内容

针对现有技术的缺陷，本发明提供一种面向大规模图数据发布的隐私保护方法及系统，其目的在于，将整体的图数据匿名保护所需时间大幅度降低，做到了匿名化过程的高效性；最终的匿名图满足k匿名机制，做到了匿名化的安全性。该发明保证了匿名图在可用性、安全性、高效性三者的平衡性能大幅度提升。

为了实现上述目的，本发明提供了一种面向大规模图数据的隐私保护方法，所述包括以下步骤：

一种面向大规模图数据发布的隐私保护方法，所述方法包括以下步骤：

(1)图分割步骤：将原图数据均匀地划分为k个子块，记录子块间由于块划分导致的被切割连边信息；

(2)连边保留步骤：读取被切割连边，比较被切割连边两端的节点度大小，在节点度较大的节点所属子块内新增噪声节点，通过节点度较大的节点与噪声节点连线实现对被切割连边的保留；

(3)子块同构步骤：聚合k个子块的结构信息，构造出同构块矩阵T；将k个子块结构信息分别与同构块矩阵T比较，并以添加噪声边的方式进行同构，使得同构后的k个子块的邻接矩阵与矩阵T相等，完成图数据匿名保护。

进一步地，所述步骤(3)中构造同构块矩阵T的具体实施方式为：

(3-1)统计各k个子块包含的最多节点数，记为max；

(3-2)分别在各k个子块内，将各节点按照节点度升序排列构成节点序列；

(3-3)改变节点序列中节点的索引信息，使得节点的新索引值newindex满足以下公式：

newindex＝max-block.size+oldindex

其中block.size为子块包含的节点数，oldindex为子块节点的原索引值；

(3-4)在节点序列中添加噪声节点，使得每个节点序列中的节点数等于max，其中噪声节点添加至已经排好序的节点序列的首部，其索引为从0开始未被使用的索引值；

(3-5)依据节点序列构造k个子块的邻接矩阵，以矩阵相加的方式聚合k个邻接矩阵，形成同构块矩阵T。

3、根据权利要求1或2所述的面向大规模图数据发布的隐私保护方法，其特征在于，所述步骤(3)中同构的具体实施方式为：

对比各子块的邻接矩阵与同构块矩阵T差异；如果矩阵T中第i行，第j列的值T_ij大于等于1并且对应子块的邻接矩阵中第i行第j列的值N_ij等于0，则在子块节点序列的第i个节点n_i和第j个节点n_j之间构造噪声边e_ij。

进一步地，在图分割步骤前还对原图数据进行模块化处理，具体为：

根据原图数据的结构信息和节点属性，计算原图的模块化程度即社区性质；若模块化程度大于阈值，则判定原图数据含有明显社区性质，将含有明显社区性质的图数据划分为多个模块数据，将各模块数据用于后续的图分割。

进一步地，所述模块化处理采用FU算法、BMLPA、SLPA、HANP中的任意一种。

进一步地，所述步骤(1)中采用多层k路划分策略将原图数据均匀的划分为k个独立的子块。

进一步地，所述步骤(2)连边保留步骤的具体实现方式为：

(2-1)读取所述被切割连边e_s-t；

(2-2)计算被切割连边e_s-t的上两端节点n_s和n_t的节点度d_s和d_t；若节点度d_s≥d_t，进入步骤(2-3)，否则进入步骤(2-4)

(2-3)则构造一个新的噪声节点n_t′,其中噪声节点n_t′索引对应于节点n_t索引，即存在一个映射关系为同时，构造一条噪声边e_s-t′,其两端节点分别为n_s和n_t′,并将构造的噪声节点n_t′以及噪声边e_s-t′一起加入节点n_s所属的子块结构信息中；

(2-4)构造一个新的噪声节点n_s′,其中噪声节点n_s′索引对应于节点n_s索引，即存在一个映射关系为同时，构造一条噪声边e_s′-t,其起两端节点分别为n_s′和n_t,并将构造的噪声节点n_s′以及噪声边e_s′-t一起加入节点n_t所属的子块结构信息中。

一种面向大规模图数据发布的隐私保护系统，所述系统包括以下模块：

图分割模块，用于将原图数据均匀地划分为k个子块，记录子块间由于块划分导致的被切割连边信息；

连边保留模块，用于读取被切割连边，比较被切割连边两端的节点度大小，在节点度较大的节点所属子块内新增噪声节点，通过节点度较大的节点与噪声节点连线实现对被切割连边的保留；

子块同构模块，用于聚合k个子块的结构信息，构造出同构块矩阵T；将k个子块结构信息分别与同构块矩阵T比较，并以添加噪声边的方式进行同构，使得同构后的k个子块的邻接矩阵与矩阵T相等，完成图数据匿名保护。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，具有以下有益效果：

(1)匿名图的高可用性：保证了原图数据上的所有节点和边的信息得以保留，即原图数据为匿名图数据的一个子集。

(2)匿名化过程的高效性：图分割目的只是将原图数据均匀的分割成k块，无需和现有技术一样,需要花费大量的时间在大规模图数据上做同构块查找操作，大幅度降低了图分割步骤在匿名化过程所占用的时间；进一步地，在图分割步骤之前，本发明优先将图数据根据其自身结构特性进行明显社区性质的划分，使得在图分割步骤中，图分割效率得到极大提升。

(3)匿名图的高安全性：保证最终的匿名图满足k匿名机制，即使得任意的一个图上相关查询，返回的结果个数不低于k。保证了任意一个潜在的攻击者在匿名图上进行重识别个体攻击的概率最大为1/k；

(4)匿名图的可用性，高效性，安全性三者的动态平衡机制得到极大改善，即能够保证高可用性，又能保证高效性的同时保证高安全性。

附图说明

图1为本发明方法流程图；

图2为本发明一实施例中图识别步骤中的两种类型的图数据示意图，其中：

图2(a)为含有明显社区性质的图数据示意图；

图2(b)为不含有明显社区性质离散分布的图数据示意图；

图3为本发明一实施例中图分割步骤中的分割示意图；

图4为本发明一实施例中连边保留步骤的示意图，其中：

图4(a)为待分割的原图数据以及连边信息示意图；

图4(b)为连边信息保留之后原图数据示意图；

图5为本发明一实例中子块同构步骤的示意图，其中：

图5(a)为连边保留步骤之后分割子块示意图；

图5(b)为由各个子块聚合形成的通过矩阵T的生成图的示意图；

图5(c)为各个子块同构化之后的生成图的示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

如图1所示，一种面向大规模图数据发布的隐私保护方法包括以下步骤：

(1)图分割步骤：将原图数据均匀地划分为k个子块，记录子块间由于块划分导致的被切割连边信息；

(2)连边保留步骤：读取被切割连边，比较被切割连边两端的节点度大小，在节点度较大的节点所属子块内新增噪声节点，通过节点度较大的节点与噪声节点连线实现对被切割连边的保留；

(3)子块同构步骤：聚合k个子块的结构信息，构造出同构块矩阵T；将k个子块结构信息分别与同构块矩阵T比较，并以添加噪声边的方式进行同构，使得同构后的k个子块的邻接矩阵与矩阵T相等，完成图数据匿名保护。

下面对各步骤详细说明：

(1)图分割步骤：

根据输入的原图数据或社区数据的结构信息，采用多层k路划分策略，将图数据均匀的划分为k块，使得每个划分后的子块的节点数和边数大致相同。图3展示了分割示意图，其中中间垂直交叉直线为多层k路划分的分割线，红色实线为各个子块原有的连边，对应的连边上的节点用灰色标注，其中各个分割后的子块分别用g₁,g₂,g₃,g₄表示。子块间原有的被删除的连边信息被单独记录下来，为保留步骤做基础的数据准备，即用List保留图3上虚线标注的连边信息，其中连边信息包括节点信息以及边的信息。本步骤中不局限于多层k路划分策略，还可采用散列算法、BHP算法、BLP算法中的任意一种。

按照一种优选的实施方式，在图分割步骤前还对原图数据进行模块化处理，具体为：根据原图数据的结构信息和节点属性，计算原图的模块化程度即社区性质；若模块化程度大于阈值，则判定原图数据含有明显社区性质，将含有明显社区性质的图数据划分为多个模块数据，将各模块数据用于后续的图分割。本发明优先将图数据根据其自身结构特性进行明显社区性质的划分，使得在图分割步骤中，图分割效率得到极大提升。

所述模块化处理采用FU算法、BMLPA、SLPA、HANP中的任意一种。下面以FU算法示例说明。通过FU算法计算原图的模块化程度，即社区性质。其中FU算法存在两个参数，及输入参数σ为决策阈值，输出参数μ为模块化系数，即μ＝FU(σ)。同时，根据计算得到的模块化系数μ，比较与给定的平均社区化系数的大小，将原图数据划分为两类，分别为含有明显社区性质的图数据以及随机或离散分布的图数据。图2(a)即为含有明显社区性质的图数据示例，其μ值大于或等于给定的模块化系数；图2(b)即为不含有明显社区性质离散分布的图数据示例，其μ值小于给定的模块化系数。

(2)连边保留步骤：

根据所述图分割中记录的被切割连边，通过比较被切割连边中的两端节点度的大小，将节点度较小的节点信息拷贝至节点度较大节点所属的子块中，拷贝方式通过添加噪声节点映射节点度较小的节点索引(这里建立索引是为了便于后续的数据复原，属于优选方式)。同时，构造一条噪声边，其一端点为原始连边上的节点度较大节点，另一端点为添加的噪声节点。

首先介绍由匿名化过程造成的信息损失的概念，由匿名化过程引起的信息损失包括节点信息损失和边信息损失。其中，节点信息损失主要包括原图上的节点在匿名图上无法找到对应节点，即原图节点被删除；边损失信息包括原图上的两个节点之间的连边经过匿名化处理之后，连边被删除或者被改变。计算匿名化过程的信息损失公式如下所示：

IL＝γ·ED(G,G^*)+δ·ND(G,G^*)(3)

公式(1)中ED(G,G^*)表示为边损失信息，G为原图数据，G^*为匿名图数据。E为原图G上边的信息，|E|为原图边的个数，表示为匿名图上，第i个子块上的边的信息，表示匿名图上k个子块上的所有边信息，则可以表示为原图和匿名图上边的交集的个数。公式(1)表示为原图与匿名图上边集的交集占原图边集的比例；公式(2)中ND(G,G^*)表示为节点损失信息，N为原图G上节点的信息，|N|为原图节点的个数，表示为匿名图上，第i个子块上的节点的信息，表示匿名图上k个子块上的所有节点信息，则可以表示为原图和匿名图上节点的交集的个数。公式(2)表示为原图与匿名图上节点集的交集占原图节点集的比例；公式(3)中，IL表示为匿名化过程中的信息损失，γ和δ分别表示为边损失信息和节点损失信息在匿名化过程中信息损失的权重。IL最终的取值范围为[0,1]。

连边保留步骤旨在将图分割步骤中产生的子块间的连边保存在某个具体的子块中。由于连边信息同时包括了原图上的节点和边的信息，如果在图分割阶段将其删除，则意味着ED(G,G^*)和ND(G,G^*)的值将根据删除量而降低。由于连边保留步骤将待删除的连边信息拷贝至具体的某个子块中，使得匿名图的信息损失IL等于1，即截止连边保留步骤阶段，原图上节点和边的信息将全部得以保留。步骤具体包括：

(2-1)读取所述被切割连边e_s-t；

(2-2)计算被切割连边e_s-t的上两端节点n_s和n_t的节点度d_s和d_t；若节点度d_s≥d_t，进入步骤(2-3)，否则进入步骤(2-4)

(2-3)则构造一个新的噪声节点n_t′,其中噪声节点n_t′索引对应于节点n_t索引，即存在一个映射关系为同时，构造一条噪声边e_s-t′,其两端节点分别为n_s和n_t′,并将构造的噪声节点n_t′以及噪声边e_s-t′一起加入节点n_s所属的子块结构信息中；

(2-4)构造一个新的噪声节点n_s′,其中噪声节点n_s′索引对应于节点n_s索引，即存在一个映射关系为同时，构造一条噪声边e_s′-t,其起两端节点分别为n_s′和n_t,并将构造的噪声节点n_s′以及噪声边e_s′-t一起加入节点n_t所属的子块结构信息中。

图4为本发明一实施例中连边保留步骤中的示意图，其中图4(a)表示一个具体的原图数据将被分割成g₁,g₂,g₃,g₄四个独立的子块，其中n₁,n₂,n₃,n₄,n₅五个节点的连边信息在图4(b)中得个保留，其被保留至g₁块中，其中灰色节点即为保留过程中与原图节点对应的噪声节点。

(3)子块同构步骤

子块同构步骤通过聚合k个子块的结构信息，构造出最终的同构块矩阵T，同时根据同构块矩阵T，将k个子块结构信息分别于矩阵T比较，以添加噪声边的方式同构，使得同构过后的k个子块的邻接矩阵与矩阵T相等，即实现了k个子块间的相互同构。

图5给出子块同构一个示例，k个独立的子块通过构造的同构矩阵T，通过增加节点和边的方式，使得各个子块与同构矩阵T的生成图同构。具体步骤包括：

(3-1)统计各k个子块包含的最多节点数，记为max；

(3-2)分别在各k个子块内，将各节点按照节点度升序排列构成节点序列；

(3-3)改变节点序列中节点的索引信息，使得节点的新索引值newindex满足以下公式：

newindex＝max-block.size+oldindex

其中block.size为子块包含的节点数，oldindex为子块节点的原索引值；

(3-4)在节点序列中添加噪声节点，使得每个节点序列中的节点数等于max,，其中噪声节点添加至已经排好序的节点序列的首部，其索引为从0开始未被使用的索引值；

(3-5)依据节点序列构造k个子块的邻接矩阵，以矩阵相加的方式聚合k个邻接矩阵，形成同构块矩阵T；

(3-6)对比各子块的邻接矩阵与同构块矩阵T差异；如果矩阵T中第i行，第j列的值T_ij大于等于1并且对应子块的邻接矩阵中第i行第j列的值B_ij等于0，则在子块节点序列的第i个节点n_i和第j个节点n_j之间构造噪声边e_ij。继续遍历，直到所有的子块最终的邻接矩阵相等，即各个子块间相互同构。

表1展示了图5(a)中各个子块按照节点度数进行升序排序的序列信息以及新旧索引的映射信息。

表1

g_i序列映射<新索引，旧索引>g₁5,6,1,2,4,3(1,5)(2,6)(3,1)(4,2)(5,4)(6,3)g₂1,4,5,3,2(1,-)(2,1)(3,4)(4,5)(5,3)(6,2)g₃1,2,4,5,3(1,-)(2,1)(3,2)(4,4)(5,5)(6,3)g₄1,2,4,5,6,3(1,1)(2,2)(3,4)(4,5)(5,6)(6,3)

根据各个子块节点序列构造的邻接矩阵为：

则同构矩阵T通过如下公式计算可得：

而后，根据步骤(3-5)，以T矩阵为模板，分别通过增加边的方式，填充各个子块，使得各个子块构成的最终邻接矩阵相同，即各个子块的图结构相互同构，如图5(c)所示。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。